回溯法详解以及剪枝优化 以leetcode 77.组合问题为例

题目描述

回溯法的简单介绍

回溯法是为了一类特定的问题概括起来就是集合里面根据要求搜索集合（不止一个），拿leetcode77.来举例，可以用多层for循环进行构思，但是要多少层呢，同时层数太多会导致时间复杂度急剧增高。因此回溯法出现可以使得这个难度降低
可以解决以下几类问题：

个人感觉回溯法的过程是下面这样的
例 在1，2，3，4这个集合中找到元素个数为2的集合

• 这个在数学上就是一个组合问题
• 我们在手动模拟计算子集问题是按照1先开始找1，2 1，3 1， 4这三个集合
• 以2开始往后找 2，3 2，4
• 以3开始往后找3， 4

因此回溯法就是这样的思路，将这个过程抽象成一个树的结构就非常好理解

以此例为例是树形结构是这样的

因此我们用回溯法解决问题时的套路也是比较固定的

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

代码实现

还有一个问题就是回溯，我觉得回溯最主要的原因是数组是共用的，所以必须回退

class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;

public:
    void backtracking(int n, int k, int start_index)
    {
        if(path.size()==k)
        {	// 终止条件
            result.push_back(path);
            return;
        }
        for(int i=start_index; i <= n-(k-path.size())+1; i++)
        {
            path.push_back(i);
            backtracking(n, k, i+1);
            path.pop_back(); // 进行回退
        }
        return;
    }
    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        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