回溯算法理论基础

回溯算法就是递归
回溯算法是暴力搜索算法
适用问题：

组合（不强调元素的顺序）
切割
子集
排列问题（排列强调元素的顺序）
棋盘问题（N皇后，解数独）

回溯法都可以抽象为一个树形结构
树的宽度=集合的大小

回溯法模板：

void backtracking(参数) {
    if (终止条件) {
        收集结果;
        return;
    }
    for (集合元素集) {
        处理节点;
        递归函数;
        回溯;
    }
    return;
}

刷题笔记day24

77.组合

文章讲解：代码随想录
是否自己做出来通过全部用例：否

遇到的困难/犯的错误

递归逻辑不是很清晰，有待理解。

自己写的代码

看了题解后写的代码：

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    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();
        }
        return;
    }
    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
};

看了题解后的收获

熟悉回溯模板。