78. 子集

这道题和前几题有些不一样，前几题都是有条件的收集路径path。比如对路径path的大小加一限制，或者对路径path的和加以限制。但是在这道题中对路径path没有任何限制，只需要我们在取出一个值后，将值输入result中，再从剩余元素中取一值，不断递归回溯。

class Solution {

private:

vector> result;

vector path;

void backtracking(vector nums,int startIndex)

{

//将path赋值给result时不需要加任何限制

result.push_back(path);

//每个for循环都是在遍历同一层

for(int i=startIndex;i

{

path.push_back(nums[i]);

backtracking(nums,i+1);

path.pop_back();

}

}

public:

vector> subsets(vector& nums) {

backtracking(nums, 0);

return result;

}

};

90. 子集 II 

 

这道题和力扣第40题类似，都需要对数组进行排序后，修剪掉同层的相同元素，保证组合不重复。 那什么时候是在遍历同层元素呢？当i>startIndex时就是在遍历同层元素。可以看看我上篇文章第40题的解析，可以了解到什么在遍历同层、什么时候在遍历同枝。

class Solution {

public:

vector path;

vector> ans;

void backtracking(vector nums,int startIndex)

{

ans.push_back(path);

for(int i=startIndex;i

{

//去掉同层相同的元素

if(i>startIndex && nums[i]==nums[i-1]) continue;

path.push_back(nums[i]);

backtracking(nums,i+1);

path.pop_back();

}

}

vector> subsetsWithDup(vector& nums) {

sort(nums.begin(),nums.end());

backtracking(nums,0);

return ans;

}

};

491. 递增子序列 

 

这题也是从集合中不断取值，题目要求结果不能出现重复的集合，所以要进行去重操作。但是这题的去重和前几题又有一些不同，前面都是可以先排序然后再去重。这题要求返回子序列，排序后子序列就改变了，所以不能排序。需要同层去重，如果我们可以记录同一层中哪些元素已经使用过了，然后再遍历新的元素时查看该元素的值是否被使用过。那么问题就解决了。

于是我们用一个集合来记录哪些元素已经使用过了

class Solution {

public:

vector path;

vector> ans;

void backtracking(vector nums,int startIndex)

{

if(path.size()>=2)

ans.push_back(path);

unordered_set used;//创建一个集合来存放一些已经使用过的值

for(int i=startIndex;i

{

if(path.size()>0 && nums[i]

//如果该值在used集合中出现过，表示它已经被使用过了，舍弃

//find（key）函数如果没找到键值key会返回迭代器end

if(used.find(nums[i])!=used.end()) continue;

path.push_back(nums[i]);

used.insert(nums[i]);

backtracking(nums,i+1);

path.pop_back();

}

}

vector> findSubsequences(vector& nums) {

backtracking(nums,0);

return ans;

}

};

！！！错误代码 

class Solution {

public:

vector path;

vector> ans;

unordered_set used;

void backtracking(vector nums,int startIndex)

{

if(path.size()>=2)

ans.push_back(path);

used.clear();//used设为全局变量导致这里清空的话，那上一层的记录也全部被清空了，used变量将毫无作用，等于没写

for(int i=startIndex;i

{

if(path.size()>0 && nums[i]

//如果该值在used集合中出现过，表示它已经被使用过了，舍弃

//find（key）函数如果没找到键值key会返回迭代器end

if(used.find(nums[i])!=used.end()) continue;

path.push_back(nums[i]);

used.insert(nums[i]);

backtracking(nums,i+1);

path.pop_back();

}

}

vector> findSubsequences(vector& nums) {

backtracking(nums,0);

return ans;

}

};

46. 全排列 

 

这道题是排列，排列和组合不一样。排列有序，组合无序。比较简单的思路就是当取出一个元素后，我们就将这个元素移除，然后再剩余的元素中再取值，直到没有剩余的元素了。

class Solution {

public:

vector path;

vector> ans;

void backtracking(vector nums)

{

if(nums.empty())

{

ans.push_back(path);

return;

}

for(int i=0;i

{

path.push_back(nums[i]);

//移除取过的元素

vector temp=nums;

temp.erase(temp.begin()+i);

backtracking(temp);

path.pop_back();

}

}

vector> permute(vector& nums) {

backtracking(nums);

return ans;

}

};

第二种方法是用一个数组来记录已经已经使用过的元素

class Solution {

public:

vector path;

vector> ans;

void backtracking(vector nums,vector used)

{

if(path.size()==nums.size())

{

ans.push_back(path);

return;

}

for(int i=0;i

{

if(used[i]==true) continue;

path.push_back(nums[i]);

//标记使用过的元素

used[i]=true;

backtracking(nums,used);

path.pop_back();

used[i]=false;

}

}

vector> permute(vector& nums) {

vector used(nums.size(),false);

backtracking(nums,used);

return ans;

}

};

47. 全排列 II 

 

相较于上一题，这题多了一步去重的操作。我们可以在排序后直接用used进行同层去重，和之前的题目一样，如果前一个元素的used值为false，说明两个元素处于同层。 

class Solution {

public:

vector path;

vector> ans;

void backtracking(vector nums,vector used)

{

if(path.size()==nums.size())

{

ans.push_back(path);

return;

}

for(int i=0;i

{

//同层去重

if(i>0 && used[i-1]==false && nums[i]==nums[i-1]) continue;

//这个是对自己进行去重，防止再取到自己

if(used[i]==true) continue;

path.push_back(nums[i]);

//标记使用过的元素

used[i]=true;

backtracking(nums,used);

path.pop_back();

used[i]=false;

}

}

vector> permuteUnique(vector& nums) {

sort(nums.begin(),nums.end());

vector used(nums.size(),false);

backtracking(nums,used);

return ans;

}

};

 

 

 

相关链接

评论可见，请评论后查看内容，谢谢！！！
 您阅读本篇文章共花了：