491. 递增子序列
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
33
34
35
36
37
38
class Solution {
public:
vector<int> path;//储存某个单一子序列
vector<vector<int> > ans;//答案集合
//回溯三部曲
//1.确认返回类型、参数
void backtracing(vector<int>& nums, int startIndex)
{
//2.中止条件，如果path长度大于等于2了加入答案集合
if(path.size() >= 2)
{
ans.emplace_back(path);
}
//3.每次回溯的遍历过程
//这个哈希表只是服务于一次回溯的遍历过程，也就是同一层，但再往下一层回溯时，是可以出现重复数字的
unordered_map<int, int> m;
for(int i = startIndex; i < nums.size(); i++)
{
//先判断是否是递增的,如果不递增，直接继续,或者同一层已经出现过了（为了去重）
//注意，递增是要和path的最后一个数字对比，不是和数组的上一个对比
if(( path.size() && nums[i] < path.back() )|| m.count(nums[i])) continue;
else
{
path.emplace_back(nums[i]);
m[nums[i]]++;
backtracing(nums, i + 1);
path.pop_back();
}
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracing(nums, 0);
return ans;
}
};
注意，递增是要和path的最后一个数字对比，不是和数组的上一个对比，用参数传递序列最后一位，不如直接用path.back()。
注意去重，去掉同一层相同的数字。
46. 全排列
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
33
34
35
36
37
38
class Solution {
public:
vector<int> path;
vector< vector<int>> ans;
//用来记录数字是否使用过
unordered_map<int, int> m;
//经典回溯三部曲
//1.确认返回类型和参数
void backtracing(vector<int>& nums)
{
//2.中止条件
if(path.size() == nums.size())
{
ans.emplace_back(path);
}
//3.每次回溯的遍历过程
for(int i = 0; i < nums.size(); i++)
{
//如果这个数字用过
if(m.count(nums[i])) continue;
else
{
m[nums[i]]++;
path.emplace_back(nums[i]);
backtracing(nums);
//当一个分支回溯完了，那么将该数退出
path.pop_back();
//也要在表中删除
m.erase(nums[i]);
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
backtracing(nums);
return ans;
}
};
我用了哈希表来存值判断是否使用过，我看可以用一个bool数组来判断是否用过这个数字，空间应该会节省更多。