回溯法

LeetCode上几个经典的回溯例题,包括全排列,子集,组合总和。可以看出不同的剪枝方式,和输出结果的时机。

78.子集

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
[3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

start的设置在剪枝上的作用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<vector<int>> ans;
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> track;
backtrack(track, nums, 0);
return ans;
}
void backtrack(vector<int>& track, vector<int>& nums, int start){
ans.push_back(track);
for(int i = start; i < nums.size(); i++){
track.push_back(nums[i]);
backtrack(track, nums, i+1);
track.pop_back();
}
}
};

90.子集2

给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

这边出现了重复元素的情况,第一步是sort之后把重复元素排列在一起,nums[i] == nums[i-1]这个条件挺好理解的,关键是!used[i-1],为什么记录nums中元素使用情况的used为false的时候,下一个同样值的元素不能push进track,是因为每次回溯回退的时候track.pop_back(); used[i] = false;。举个例子,对于[1,2,2]来说,track状态为[1]时候,第一个2进入,输出了[1,2]之后,经过pop,此时 第一个2的used状态修改成false,并且此时track又回溯成[1]。这时候for循环到了第二个2,如果我们再输出一个[1,2]显然就重复输出了。对于这个例子,used[i-1]为 true的情况是,我们需要输出[1,2,2]的时候,这时候我们允许第二个2进入track。

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<vector<int>> ans;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<int> track;
sort(nums.begin(), nums.end());
vector<bool> used(nums.size(), false);
backtrack(nums, track, used, 0);
return ans;

}
void backtrack(vector<int>& nums, vector<int>& track, vector<bool>& used, int start){
ans.push_back(track);
for (int i = start; i < nums.size(); i++){
if (used[i] || (i>start && nums[i] == nums[i-1]&& !used[i-1])){
continue;
}
track.push_back(nums[i]);
used[i] = true;
backtrack(nums, track, used, i+1);
track.pop_back();
used[i] = false;
}
}
};

46.全排列

给定一个 没有重复 数字的序列,返回其所有可能的全排列。
示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

47.全排列2

给定一个可包含重复数字的序列,返回所有不重复的全排列。
示例:

1
2
3
4
5
6
7
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
vector<vector<int>> ans;
vector<vector<int>> permute(vector<int>& nums) {
vector<int> track;
backtrack(nums, track);
return ans;
}
void backtrack(vector<int>& nums, vector<int>& track){
if (track.size() == nums.size()){
ans.push_back(track);
}
for (int i = 0; i < nums.size(); i++){
if (find(track.begin(), track.end(), nums[i]) != track.end())
continue;
track.push_back(nums[i]);
backtrack(nums, track);
track.pop_back();
}

}
};

39.组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

所有数字(包括 target)都是正整数。
解集不能包含重复的组合。
示例 1:

1
2
3
4
5
6
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]

示例 2:

1
2
3
4
5
6
7
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
vector<vector<int>> ans;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> track;
//sort(candidates.begin(), candidates.end());
backtrack(candidates, track, target, 0);
return ans;
}
void backtrack(vector<int>& candidates, vector<int>& track, int target, int start){
if (target == 0 ){
ans.push_back(track);
return;
}
if (target < 0) return;
for(int i = start; i < candidates.size(); i++){
if (candidates[i] > target) continue;
track.push_back(candidates[i]);
backtrack(candidates, track, target-candidates[i], i);
track.pop_back();
}
}
};

40.组合总和2

给定一个有重复元素的数组 candidates

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<vector<int>> ans;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> track;
sort(candidates.begin(), candidates.end());
//vector<bool> used(track.size(), false);
backtrack(candidates, track, target, 0);
return ans;
}
void backtrack(vector<int>& candidates, vector<int>& track, int target, int start){
if (target == 0 ){
ans.push_back(track);
return;
}
if (target < 0) return;
for(int i = start; i < candidates.size(); i++){
if (candidates[i] > target || ( i>start && candidates[i] == candidates[i-1]) ) continue;
track.push_back(candidates[i]);
backtrack(candidates, track, target-candidates[i], i+1);
track.pop_back();
}
}
};