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();
            }
        }
    }
};

ciicA BOCer

个人简介