淘宝店做网站建设不能开直通车,企业网站源码自适应,教程网站后台密码,织梦网站首页打开慢给你一个整数数组 nums #xff0c;找出并返回所有该数组中不同的递增子序列#xff0c;递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素#xff0c;如出现两个整数相等#xff0c;也可以视作递增序列的一种特殊情况。
示例 1#…给你一个整数数组 nums 找出并返回所有该数组中不同的递增子序列递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素如出现两个整数相等也可以视作递增序列的一种特殊情况。
示例 1
输入nums [4,6,7,7]
输出[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
示例 2
输入nums [4,4,3,2,1]
输出[[4,4]] 1 回溯算法哈希表 使用 uset 来记录每层递归里已经取过的元素来避免重复取数
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint nums,int startIndex) {if(path.size()1) {result.push_back(path);// 注意这里不要加return要取树上的节点}unordered_setint uset; // 使用set来对本层元素进行去重for(int istartIndex;inums.size();i) {if((!path.empty() nums[i]path.back()) || uset.find(nums[i]) ! uset.end()) continue;uset.insert(nums[i]); // 记录这个元素在本层用过了本层后面不能再用了path.push_back(nums[i]);backtracking(nums,i1);path.pop_back();}}vectorvectorint findSubsequences(vectorint nums) {backtracking(nums, 0);return result;}
};
2优化由于数值范围[-100,100]可以用数组来做哈希提升效率
int used[201] {0}; // 这里使用数组来进行去重操作题目说数值范围[-100, 100]
for (int i startIndex; i nums.size(); i) {if ((!path.empty() nums[i] path.back()) || used[nums[i] 100] 1) {continue;}used[nums[i] 100] 1; // 记录这个元素在本层用过了本层后面不能再用了......
}
参考文章和推荐视频
代码随想录 (programmercarl.com)https://www.programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html#%E4%BC%98%E5%8C%96回溯算法精讲树层去重与树枝去重 | LeetCode491.递增子序列_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1EG4y1h78v/?spm_id_from333.788vd_sourcea934d7fc6f47698a29dac90a922ba5a3
