代码随想录 Day24 理论基础 77. 组合

理论基础

1. 回溯是配合递归算法进行使用的，一般是在递归的下面。回溯的算法是一种暴力的算法，虽然效率并不高，但是常常使用。因为很多时候使用多层for（因为层数实在是套多了）也不能将题目解答，这个时候就需要使用到递归回溯算法。

2. 回溯算法可以解决的问题，回溯算法可以解决组合，排列，切割，子集，棋盘问题，在这些问题上使用回溯算法有着很好的效果。

组合：1234一个四个数，对于他们进行两两组合

排列：对于上述的组合建立一个顺序，进行排列

切割：将一个字符串进行切割成几种情况。

子集：1234一共四个数，去求它的子集。

棋盘问题：就是像是N皇后等。

3. 回溯算法一般都是可以抽象为一棵树

4. 回溯模型的模板：依然是三部曲

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

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

首先是函数和参数：一般是用backtracking(参数)

接下来就是终止情况：进行判断，如果是终止条件的话就存放结果并返回

最后是核心代码去：（这个地方还不是很理解，后面借助于例子再好好理解一下）

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。

backtracking这里自己调用自己，实现递归。

大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

77. 组合

class Solution {
private:
    vector<vector<int>> result; // 存放符合条件结果的集合
    vector<int> path; // 用来存放符合条件结果
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n; i++) {
            path.push_back(i); // 处理节点
            backtracking(n, k, i + 1); // 递归
            path.pop_back(); // 回溯，撤销处理的节点
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        result.clear(); // 可以不写
        path.clear();   // 可以不写
        backtracking(n, k, 1);
        return result;
    }
};

思路: 本题的思路还是比较难的，想要理解本题必须要画一棵树