78. 子集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
vector<int> path;//储存每一个组合
vector<vector<int> > ans;//子集
//1.回溯三部曲，确认返回类型、参数
void backtracing(vector<int>& nums, int startIndex)
{
//2.中止条件
//因为每个组合都要存放在子集中，所以每次都要保存，所以其实是没有中止条件的
ans.emplace_back(path);
//3.每次回溯的遍历过程
for(int i = startIndex; i < nums.size(); i++)
{
path.emplace_back(nums[i]);
backtracing(nums, i + 1);
path.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
backtracing(nums, 0);
return ans;
}
};
backtracing(nums, i + 1);一开始写成了backtracing(nums, startIndex + 1);结果不对，传给下一次回溯的应该是当前i的下一位，startInde下一位的话，会有重复的内容。
90. 子集 II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
//树层去重方法
vector<int> path;//储存每一个组合
vector<vector<int> > ans;//子集
//1.回溯三部曲，确认返回类型、参数
void backtracing(vector<int>& nums, int startIndex)
{
//2.中止条件
//因为每个组合都要存放在子集中，所以每次都要保存，所以其实是没有中止条件的
ans.emplace_back(path);
//3.每次回溯的遍历过程
for(int i = startIndex; i < nums.size(); i++)
{
path.emplace_back(nums[i]);
backtracing(nums, i + 1);
//去重,保证当前位置的数字与下一个不一样
while(i < nums.size() - 1 && nums[i] == nums[i + 1]) i++;
path.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
//需要先对数组排序
sort(nums.begin(), nums.end());
//回溯
backtracing(nums, 0);
return ans;
}
};
这个要注意去重代码的位置，去重应该是这一根树枝已经回溯完了，要回溯下一根树枝时去重，这样去掉的才是统一树层中的相同树枝。
我开始把去重放在了for循环的开始，这样是不对的，会少很多组合。