190.回溯算法：组合（力扣）

代码随想录 (programmercarl.com)

一、什么是回溯算法

        回溯算法是一种通用的算法设计技巧，特别适用于解决组合、排列、子集等问题。它通过逐步构建解决方案，并在发现部分解决方案无效时撤销（回溯）部分计算，从而寻找所有可能的解决方案。

        回溯算法的基本思想是通过深度优先搜索（DFS）遍历所有可能的解空间，当发现某条路径不符合条件时，返回到上一步，尝试其他路径。

二、回溯法解决的问题

回溯法，一般可以解决如下几种问题：

• 组合问题：N个数里面按一定规则找出k个数的集合
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，解数独等等

三、如何理解回溯法

        回溯法解决的问题都可以抽象为树形结构，因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

四、回溯三部曲 

• 回溯函数模板返回值以及参数

void backtracking(参数)

• 回溯函数终止条件

if (终止条件) {
    存放结果;
    return;
}

• 回溯搜索的遍历过程

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

完整模板如下

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

力扣题目

 

代码解决 

class Solution {
public:
    vectorint>> result;  // 存储所有组合结果
    vector<int> path;  // 存储当前组合路径
 
    // 回溯函数
    void backtracking(int n, int k, int index) {
        // 如果当前路径长度等于k，则找到一个有效组合，将其加入结果集
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
 
        // 从当前索引开始遍历到n
        for (int i = index; i <= n; i++) {
            path.push_back(i);  // 选择当前数加入组合路径
            backtracking(n, k, i + 1);  // 递归调用，继续选择下一个数
            path.pop_back();  // 撤销选择，回溯到上一步
        }
    }
 
    // 主函数，生成1到n中k个数的所有组合
    vectorint>> combine(int n, int k) {
        backtracking(n, k, 1);  // 从1开始进行回溯
        return result;  // 返回所有组合结果
    }
};

代码使用了回溯算法。主要思路是使用一个递归函数 backtracking 来生成所有可能的组合。在每次递归调用中，我们选择一个数并将其添加到当前组合中，然后递归地继续选择下一个数。如果当前组合的长度达到k，则将其添加到结果集中。在每次递归调用之前，我们通过将当前数从路径中移除来实现回溯。

这里简要解释一下代码的工作流程：

1. 定义两个全局变量 result 和 path，分别用于存储所有组合结果和当前组合路径。
2. 定义一个辅助函数 backtracking，它接受三个参数：n（数列的上限）、k（组合中元素的数量）和当前选择的起始索引 index。
3. 如果当前路径长度等于k，则找到了一个有效的组合，将其加入结果集 result。
4. 从当前索引 index 开始遍历到n，对于每个数，将其添加到路径 path 中，然后递归调用 backtracking 函数继续选择下一个数。
5. 在每次递归调用之前，通过 path.pop_back() 撤销选择，实现回溯。
6. 在 combine 函数中，调用 backtracking 函数开始生成所有可能的组合，并返回结果集 result。

这个算法的时间复杂度是 O(n * k)，因为需要生成所有可能的k个数的组合。空间复杂度也是 O(n * k)，因为需要存储所有组合和递归调用的栈。