LeetCode-backtrack类总结

本文主要是对leetcode中的backtracking类算法的总结,包含了各题的solution和常用解法。

相关源码:code

回溯法直观的理解:受限的分治算法

78. Subsets

Description:

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

1
2
3
4
5
6
7
8
9
10
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(),nums.end());
vector<int> tmp;
backtrack(res, tmp, nums, 0);
return res;
}

void backtrack(vector<vector<int>> &res, vector<int> &temp, vector<int> &nums, int start){
res.push_back(temp);
for(int i=start;i<nums.size();i++){
temp.push_back(nums[i]);
backtrack(res, temp,nums,i+1);
temp.pop_back();
}
}
};

90. Subsets II

Description:

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

1
2
3
4
5
6
7
8
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(),nums.end());
vector<int> tmp;
subsets(res,tmp, nums, 0);
return res;
}

void subsets(vector<vector<int>> &res, vector<int> &temp, vector<int> &nums, int start){
res.push_back(temp);
for(int i=start;i<nums.size();i++){
if(i>start && nums[i]==nums[i-1]) continue;
temp.push_back(nums[i]);
subsets(res,temp,nums,i+1);
temp.pop_back();
}
}
};

46. Permutations

Description:

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

1
2
3
4
5
6
7
8
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

solution:

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
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
vector<int> tmp;
backtrack(res, tmp, nums);
return res;
}

void backtrack(vector<vector<int>> &res, vector<int> temp, vector<int> &nums){
if(temp.size()==nums.size()) res.push_back(temp);
else{
for(int i=0; i<nums.size();i++){
if(contain(temp, nums[i])) continue;
temp.push_back(nums[i]);
backtrack(res,temp,nums);
temp.pop_back();
}
}
}

bool contain(vector<int> &nums, int target){
for(int i=0; i<nums.size();i++){
if(nums[i]==target) return true;
}
return false;
}
};

47. Permutations II

Description:

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:

1
2
3
4
5
[
[1,1,2],
[1,2,1],
[2,1,1]
]

solution:

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>> permuteUnique(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<int> tmp;
vector<bool> used(nums.size(), false);
vector<vector<int>> res;
backtrack(res, tmp, nums, used);
return res;
}

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

39. Combination Sum

Description:

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

1
2
3
4
5
[
[7],
[2, 2, 3]
]

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
sort(candidates.begin(),candidates.end());
vector<int> tmp;
backtrack(res, tmp, candidates,target, 0);
return res;
}

void backtrack(vector<vector<int>> &res, vector<int> &temp, vector<int> &candidates, int remain, int start){
if(remain<0) return;
else if(remain==0) res.push_back(temp);
else{
for(int i=start; i<candidates.size(); i++){
temp.push_back(candidates[i]);
backtrack(res, temp, candidates, remain-candidates[i], i);
temp.pop_back();
}
}
}
};

40. Combination Sum II

Description:

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:

1
2
3
4
5
6
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

solution:

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>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> res;
sort(candidates.begin(),candidates.end());
vector<int> tmp;
backtrack(res, tmp, candidates, target, 0);
return res;
}

void backtrack(vector<vector<int>> &res, vector<int> &temp, vector<int> nums, int remain, int start){
if(remain<0) return;
else if(remain==0) res.push_back(temp);
else{
for(int i=start; i<nums.size(); i++){
if(i>start && nums[i]==nums[i-1]) continue;
temp.push_back(nums[i]);
backtrack(res, temp, nums, remain-nums[i], i+1);
temp.pop_back();
}
}
}
};