回溯算法

回溯算法

如何区别DFS和回溯算法

DFS 是一个劲的往某一个方向搜索，而回溯算法建立在 DFS 基础之上的，但不同的是在搜索过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索。回溯算法与 DFS 的区别就是有无状态重置

全排列

全排列

这是一个较为简单的排列组合问题，因为之前我们做过类似的题目，就是简单的回溯算法，所以直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    void BackInt(vector<vector<int>>& res,vector<int>& output, int first,int len){
        if(first == len){
            res.push_back(output);
             return;
        }
        for(int i = first; i < len;++i){
            swap(output[i],output[first]);
            BackInt(res,output,first+1,len);
            swap(output[i],output[first]); //回溯算法的魅力
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        BackInt(res,nums,0,(int)nums.size());
        return res;
    }
};

所以我选择图解，然后就会比较好接受
图解

我个人感觉回溯算法还是有点难理解，但是利用dfs的话，相对来说就会比较容易理解，它和全排列（去重）的模板本质是差不多的

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>> result;
    vector<int> path;
    void backtracking (vector<int>& nums, vector<bool>& used) {
        // 此时说明找到了一组
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i] == true) continue; // path里已经收录的元素，直接跳过
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(), false);  //利用这个来确定是否访问过
        backtracking(nums, used);
        return result;
    }
};

全排列（去重）

全排列

对于这些直接利用上面的模板，直接回溯算法

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 {
    vector<int> vis;
public:
    void backtrack(vector<int>& nums, vector<vector<int>>& ans, int idx, vector<int>& perm) {
        if (idx == nums.size()) {
            ans.emplace_back(perm);
            return;
        }
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {//这个就是用来确认是否访问过或者是相同的元素
                continue;
            }
            perm.emplace_back(nums[i]);
            vis[i] = 1;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = 0;
            perm.pop_back();  //回溯
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> perm;
        vis.resize(nums.size());
        sort(nums.begin(), nums.end());
        backtrack(nums, ans, 0, perm);
        return ans;
    }
};

组合总和


回溯算法图解


两种方式直接上两种代码：

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    vector<vector<int>> result;
    vector<int> num;
    void dfs(vector<int>& candidates,int idx,int target){
        if(idx == candidates.size()){
            return ;
        }
        if(target == 0){
            result.push_back(num);
            return ;
        }
        dfs(candidates,idx+1,target);  //这一个步骤主要是为了跳过，应该要去好好理解
        if(target-candidates[idx] >= 0){
            num.emplace_back(candidates[idx]);
            dfs(candidates,idx,target-candidates[idx]);
            num.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int n = candidates.size();
        dfs(candidates, 0, target);
        return result;
    }
};


class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
            return;
        }
        // 如果 sum + candidates[i] > target 就终止遍历
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i);
            sum -= candidates[i];
            path.pop_back();

        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        sort(candidates.begin(), candidates.end()); // 需要排序
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

组合总和（去重）

跟上面的差不多，只是需要一个判断条件

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
class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
            return;
        }
        // 如果 sum + candidates[i] > target 就终止遍历
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            if(i > startIndex && candidates[i] == candidates[i-1])continue; //判断是否有相同的数
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i+1);
            sum -= candidates[i];
            path.pop_back();

        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end()); // 需要排序
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

组合

图解

上代码：这种主要在剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> result;
    vector<int> num;
    void dfs(int start, int n, int k){
        if(k == num.size()){
            result.push_back(num);
            return ;
        }
        for(int i = start;i <= n-(k-num.size())+1;++i){ 
        //剪枝，i <= n-(k-num.size())+1 这个处理的很好
            num.push_back(i);
            dfs(i+1,n,k);
            num.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        dfs(1,n,k);
        return result;
    }
};

子集

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

子集（去重）

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
class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {
        result.push_back(path);
        for (int i = startIndex; i < nums.size(); i++) {
            // used[i - 1] == true，说明同一树支candidates[i - 1]使用过
            // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
            // 而我们要对同一树层使用过的元素进行跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, i + 1, used);
            used[i] = false;
            path.pop_back();
        }
    }

public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end()); // 去重需要排序
        backtracking(nums, 0, used);
        return result;
    }
};

总结

整体来说，回溯算法确实比较简单，主要有些题目的想法，在我写着这个的时候，我也发现别人写的代码和自己写的代码是有差距的，因此有些代码我是改过的，符合自己的想法，比如说去重，就是一个简单bool数组来判断，根据不同的人选取不同的方法。有些我确实比较难于理解

一、何时使用回溯算法

当问题需要 “回头”，以此来查找出所有的解的时候，使用回溯算法。即满足结束条件或者发现不是正确路径的时候(走不通)，要撤销选择，回退到上一个状态，继续尝试，直到找出所有解为止

二、怎么样写回溯算法(从上而下，※代表难点，根据题目而变化)

  • ①画出递归树，找到状态变量(回溯函数的参数)，这一步非常重要※
  • ②根据题意，确立结束条件
  • ③找准选择列表(与函数参数相关),与第一步紧密关联※
  • ④判断是否需要剪枝
  • ⑤作出选择，递归调用，进入下一层
  • ⑥撤销选择

本文参考