非递减子序列
问题描述
给了一个数组，要求给出其所有长度>=2的非递减子序列。
思路
压入结果的条件是path.size()>=2，回溯过程结束的条件是移动到了边上startIndex>=num.size()
在树中，非递减序列，要求压入的元素必须比之前压入的大：if(path.empty()||nums[i]>=path.back())
问题
如果给出的数组包含重复元素，那么答案的集合中就会包含重复的数组；
那我标记该位置的元素已经用过了，如何？````
if(used[i]==false&&(path.empty()||nums[i]>=path.back())){path.push_back(nums[i]);used[i]=true;backtrack(nums,i+1,used);path.pop_back();used[i]=false;}
这样也是不行的，原因在于数组不同下标处的元素可能相等，这样只是标记了一个位置的该元素，但是如果该位置后面的元素和已经遍历过的元素有相同的，也会导致结果集中存在一样的数组。所以重点不是对下标记录，而是对这个元素本身的值进行记录。使用哈希容器unorder_set<int> usedThisLeval
for(int i=startIndex;i<nums.size();i++){if(usedThisLeval.contains(nums[i])){continue;}if(path.empty()||nums[i]>=path.back()){path.push_back(nums[i]);usedThisLeval.insert(nums[i]);backtrack(nums,i+1);path.pop_back();}}
但是似乎很慢！
原始思路解法代码
class Solution {
public:vector<int>path;set<vector<int>> res;void backtrack(vector<int>&nums, int startIndex){if(path.size()>=2){res.insert(path);}if(startIndex>=nums.size()){return;}for(int i=startIndex;i<nums.size();i++){if(path.empty()||nums[i]>=path.back()){path.push_back(nums[i]);backtrack(nums,i+1);path.pop_back();}}}vector<vector<int>> findSubsequences(vector<int>& nums) {path.clear();res.clear();backtrack(nums,0);return vector<vector<int>>(res.begin(),res.end());}
};
全排列
题目描述
给定一个不含重复数字的数组，返回其所有可能的全排列。
看到题目第一眼，感觉这道题和之前做过的组合问题很相似。组合问题：在n个数中找K个数的组合。复用后发现不同，N个数的组合在组合问题中是这种情况
在回溯的这颗树中，在移动startIndex的过程中之前的数就不会考虑进来了，但是排列问题需要考虑进来。
解决办法是vector
class Solution {
public:vector<int>path;vector<vector<int>> res;void backtrack(vector<int>&nums, vector<bool>&used){if(path.size()==nums.size()){res.push_back(path);return;}for(int i=0;i<nums.size();i++){if(used[i]==true){continue;//跳出本次循环}used[i]=true;{path.push_back(nums[i]);backtrack(nums,used);path.pop_back();used[i]=false;}}}vector<vector<int>> permute(vector<int>& nums) {path.clear();res.clear();vector<bool>used(nums.size(),false);backtrack(nums,used);return res; }
};
全排列2
问题理解
数组中出现了重复元素，使用暴力set去重，但是似乎是一种很慢的方法，相当于每次插入都要遍历一次所有组合。
代码
class Solution {
public:vector<int>path;vector<vector<int>> res;void backtrack(vector<int>&nums, vector<bool>&used){if(path.size()==nums.size()){res.push_back(path);return;}for(int i=0;i<nums.size();i++){if(i>0&&nums[i]==nums[i-1]&&used[i-1]==true){continue;//跳出本次循环}if(used[i]==false){used[i]=true;path.push_back(nums[i]);backtrack(nums,used);path.pop_back();used[i]=false;}}}vector<vector<int>> permuteUnique(vector<int>& nums) {path.clear();res.clear();sort(nums.begin(),nums.end());vector<bool>used(nums.size(),false);backtrack(nums,used);return res; }
};
总结
在排列问题中使用startIndex来标记位置，因为排列是从后面每次都经过。但在组合问题中，答案集合是不关心位置的，固定元素的不同组合。首先对数组进行排序，使用used看是否用过。