代码随想录算法训练营day24|回溯理论基础、77.组合
回溯理论基础
带你学透回溯算法（理论篇）| 回溯法精讲！_哔哩哔哩_bilibili
回溯算法是一种试探性的算法，用于解决组合优化问题。这类问题通常涉及在给定的候选集中找出满足特定条件的所有解。回溯算法通过深度优先遍历的方式，探索决策树的所有可能分支，从而找出所有解，就树而言，我们很容易想到递归，递归和回溯是相辅相成的。
回溯法要解决的问题都能抽象成树形结构，也以此，回溯算法的基本思想是，从树的根节点开始，按某种顺序尝试所有可能的选择（例如，从左到右）。每做出一个选择，就生成一个新的节点，然后递归地继续进行选择。如果在某一点上发现当前的选择不满足条件（例如，超过了某个限制或违反了问题的规则），则回溯到上一个节点，并尝试其他选择。这个过程一直持续到找到所有解或遍历完所有可能性为止。因此，回溯法可以看作是枚举法的一种特殊化，在极端情况下，算法的搜索效率等于暴力枚举，即回溯法的时间复杂度较高。
回溯算法通常用于解决如下类型的问题：
- 组合问题：找出所有可能的组合（无序），例如，八皇后问题（棋盘问题）、组合数问题等。
- 切割问题：给定字符串，查找切割方式。
- 子集问题：列一个集合的所有子集等。
- 排列问题：找出所有可能的排列（有序），例如，旅行商问题、电话号码字母组合问题等。
- 决策问题：找出满足特定条件的所有决策，例如，0-1背包问题、图的着色问题等。
回溯算法的关键组成部分包括：
- 路径：记录从根节点到当前节点的选择序列。
- 选择列表：当前节点可用的所有选择。
- 结束条件：确定何时应该结束递归，并返回结果。
回溯算法的优点是，它可以系统地找出所有可能的解，并且易于理解和实现。然而，它的缺点是，对于某些问题，它可能非常耗时，特别是当问题的解空间非常大时。
在实际应用中，回溯算法经常与其他算法策略结合使用，如剪枝（通过提前排除明显不满足条件的路径来减少搜索空间）等，以提高其效率。
回溯法三部曲（参考代码随想录）
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}
组合
回溯三部曲
1.确定函数参数和返回值
2.确定终止条件
3.单层递归逻辑
class Solution {
public:// 存储所有可能的组合路径vector<vector<int>> paths;// 存储当前正在构建的路径vector<int> path;// 回溯函数void backtracking(int n, int k, int startindex) {// 如果当前路径长度等于k，说明找到了一个有效的组合if (path.size() == k) {// 将当前路径添加到所有可能的组合路径中paths.push_back(path);// 返回上一层递归return;}// 从startindex开始，尝试所有可能的数字for (int i = startindex; i <= n; i++) {// 将数字i添加到当前路径path.push_back(i);// 递归调用，尝试下一个数字backtracking(n, k, i + 1);// 回溯，撤销上一步的选择，尝试其他数字path.pop_back();}}// 主函数，用于获取所有可能的组合vector<vector<int>> combine(int n, int k) {// 从数字1开始回溯backtracking(n, k, 1);// 返回所有可能的组合路径return paths;}
};对于每个组合，我们都需要深入到叶子节点来生成完整的组合，而每个组合有k个元素。在回溯的过程中，我们每次都选择或不选择一个元素，这样的选择有n-k+1次（因为一旦我们选择了k个元素，就不会再继续选择了）。因此，对于每个组合，我们有2^(n-k+1)种可能的选择。由于我们要生成所有C(n, k)个组合，每个组合都有2^(n-k+1)种选择，所以总的时间复杂度是O(C(n, k) * 2^(n-k+1))。
空间复杂度主要取决于递归栈的深度和存储组合的路径。递归栈的最大深度是k，因为我们需要选择k个元素。存储组合的路径也需要空间，每个组合需要k个元素的存储空间。因此，空间复杂度是O(k)。