排列组合

回溯算法是什么？解决回溯算法相关的问题有什么技巧？如何学习回溯算法？回溯算法代码是否有规律可循？

其实回溯算法其实就是我们常说的 DFS 算法，本质上就是一种暴力穷举算法。

废话不多说，直接上回溯算法框架。解决一个回溯问题，实际上就是一个决策树的遍历过程。

站在回溯树的一个节点上，你只需要思考 3 个问题：

1、路径：也就是已经做出的选择。

2、选择列表：也就是你当前可以做的选择。

3、结束条件：也就是到达决策树底层，无法再做选择的条件。

如果你不理解这三个词语的解释，没关系，我们后面会用「全排列」和「N 皇后问题」这两个经典的回溯算法问题来帮你理解这些词语是什么意思，现在你先留着印象。

代码方面，回溯算法的框架：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

综合

总结

来回顾一下排列/组合/子集问题的三种形式在代码上的区别。

由于子集问题和组合问题本质上是一样的，无非就是 base case 有一些区别，所以把这两个问题放在一起看。

形式一、元素无重不可复选

即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，backtrack 核心代码如下：

 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

/* 组合/子集问题回溯算法框架 */
void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i + 1);
        // 撤销选择
        track.removeLast();
    }
}

/* 排列问题回溯算法框架 */
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 剪枝逻辑
        if (used[i]) {
            continue;
        }
        // 做选择
        used[i] = true;
        track.addLast(nums[i]);

        backtrack(nums);
        // 取消选择
        track.removeLast();
        used[i] = false;
    }
}

78. 子集

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    vector<vector<int>> res;
    vector<int> cur;
    void dfs(vector<int>& nums,int start){
        res.push_back(cur);
        for(int i =start;i<nums.size();i++){
            cur.push_back(nums[i]);
            dfs(nums,i+1);
            cur.pop_back();
        }
        
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums,0);       
        return res;
    }
};

216. 组合总和 III

 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>> res;
    vector<int> cur;
    void dfs(int start,int k, int target,int sum){
        if(target==sum&&k==0){
            res.push_back(cur);
            return;
        }       
        if(sum>target) return;
        for(int i =start;i<=9;i++){
            sum+=i;
            cur.push_back(i);
            k--;
            dfs(i+1,k,target,sum);
            sum-=i;
            cur.pop_back();
            k++;
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(1,k,n,0);
        return res;
    }
};

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

class Solution {
public:
    vector<vector<int>> res;
    vector<int> cur;
    bool st[8];
    void dfs(vector<int>& nums){
        if(cur.size()==nums.size()){
            res.push_back(cur);
            return;
        }
        for(int i =0;i<nums.size();i++){
            if(!st[i]){
                st[i]=true;
                cur.push_back(nums[i]);
                dfs(nums);
                st[i]=false;
                cur.pop_back();               
            }
        }        
    }
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums);        
        return res;
    }
};

77. 组合

 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>> res;
    vector<int> cur;
    void dfs(int start,int n,int k){
        if(cur.size()==k){
            res.push_back(cur);
            return;
        }
        for(int i = start;i<=n;i++){
            cur.push_back(i);
            dfs(i+1,n,k);
            cur.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        dfs(1,n,k);
        return res;
    }
};

形式二、元素可重不可复选

即 nums 中的元素可以存在重复，每个元素最多只能被使用一次，其关键在于排序和剪枝，backtrack 核心代码如下：

 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
39
40
41

Arrays.sort(nums);
/* 组合/子集问题回溯算法框架 */
void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 剪枝逻辑，跳过值相同的相邻树枝
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i + 1);
        // 撤销选择
        track.removeLast();
    }
}


Arrays.sort(nums);
/* 排列问题回溯算法框架 */
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 剪枝逻辑
        if (used[i]) {
            continue;
        }
        // 剪枝逻辑，固定相同的元素在排列中的相对位置
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }
        // 做选择
        used[i] = true;
        track.addLast(nums[i]);

        backtrack(nums);
        // 取消选择
        track.removeLast();
        used[i] = false;
    }
}

40. 组合总和 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

class Solution {
public:
    vector<vector<int>> res;
    vector<int> cur;
    void dfs(int start,vector<int>& candidates, int target,int sum){
        if(target==sum){
            res.push_back(cur);
            return;
        }
        if(sum>target) return;
        for(int i =start;i<candidates.size();i++){
            // 剪枝逻辑，跳过值相同的相邻树枝
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            sum+=candidates[i];
            cur.push_back(candidates[i]);
            dfs(i+1,candidates,target,sum);
            sum-=candidates[i];
            cur.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        dfs(0,candidates,target,0);
        return res;
    }
};

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

class Solution {
public:
    vector<vector<int>> res;
    vector<int> cur;
    bool st[8];
    void dfs(vector<int>& nums,int start){
        res.push_back(cur);
        for(int i =start;i<nums.size();i++){
            // 剪枝逻辑，值相同的相邻树枝，只遍历第一条
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            cur.push_back(nums[i]);
            dfs(nums,i+1);
            cur.pop_back();
        }       
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        // 先排序，让相同的元素靠在一起
        sort(nums.begin(),nums.end());
        dfs(nums,0);        
        return res;
    }
};

47. 全排列 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

class Solution {
public:
    vector<vector<int>> res;
    vector<int> cur;
    bool st[10];
    void dfs(vector<int>& nums){
        if(cur.size()==nums.size()){
            res.push_back(cur);
            return;
        }
        for(int i =0;i<nums.size();i++){
             // 剪枝逻辑，值相同的相邻树枝，只遍历第一条
            if (i > 0 && nums[i] == nums[i - 1]&& !st[i - 1]) {
                continue;
            }
            if(!st[i]){
                st[i]=true;
                cur.push_back(nums[i]);
                dfs(nums);
                st[i]=false;
                cur.pop_back();               
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        dfs(nums);
        return res;
    }
};

形式三、元素无重可复选

即 nums 中的元素都是唯一的，每个元素可以被使用若干次，只要删掉去重逻辑即可，backtrack 核心代码如下：

 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

/* 组合/子集问题回溯算法框架 */
void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i);
        // 撤销选择
        track.removeLast();
    }
}


/* 排列问题回溯算法框架 */
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);

        backtrack(nums);
        // 取消选择
        track.removeLast();
    }
}

39. 组合总和

 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>> res;
    vector<int> cur;
    void dfs(int start,vector<int>& candidates, int target,int sum){
        if(target==sum){
            res.push_back(cur);
            return;
        }
        if(sum>target) return;
        for(int i =start;i<candidates.size();i++){
            sum+=candidates[i];
            cur.push_back(candidates[i]);
            dfs(i,candidates,target,sum);
            sum-=candidates[i];
            cur.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(0,candidates,target,0);
        return res;
    }
};