认识回溯

77.组合 

认识回溯

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。

回溯是递归的副产品，只要有递归就会有回溯。

回溯法的效率

回溯的本质是穷举，即使加了剪枝操作，其本质也还是穷举

回溯法解决的问题

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

理解回溯法

回溯法解决的问题都可以抽象为树形结构

回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。

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

回溯法模板

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

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

 光看理论确实有点懵，还需要再实践中加深理解耶！

77.组合

回溯三步骤：

• 递归函数的返回值以及参数

vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件结果

• 回溯函数终止条件

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); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
    path.pop_back(); // 回溯，撤销处理的节点
}

成员变量：

• result：用于存储所有符合条件的组合集合。
• path：用于暂存当前正在探索的组合路径。

backtracking函数：是回溯算法的核心，接受三个参数：

• n：表示选择范围的上限。
• k：目标组合的长度。
• startIndex：当前递归探索的起始索引，避免重复选择。

递归逻辑：

• 终止条件：当path的长度等于k时，表示找到了一个有效的组合，将其添加到result中并返回。
• 递归遍历：从startIndex开始，遍历到n。对于每一个数i，将其添加到path中（处理节点），然后递归调用backtracking函数，探索下一个数字，起始索引为i + 1（保证不会选择到重复的数字）。递归返回后，执行回溯操作，即从path中移除最后添加的数字，以探索其他可能的组合路径。

combine函数：

• 是公共接口，用于初始化状态并调用backtracking函数开始递归探索。
• 在开始前清空result和path，确保结果集是从空开始的。虽然在题目给定的单次调用场景中，清空操作可能不是必须的，但在多次调用同一个对象的方法时，清空操作可以保证每次调用结果的独立性。
• 调用backtracking开始递归探索，并最终返回所有找到的组合。

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;
    }
};

优化 

• 剪枝逻辑：通过计算[startIndex, n]区间内剩余的选择数量是否足够满足组合长度k的需求来决定是否继续递归。这里的剪枝条件为i <= n - (k - path.size()) + 1。这个条件确保了只有当剩余的选择足够填满剩余所需的组合长度时，才继续递归。
• 效率提升：这种剪枝可以显著减少递归的次数，特别是当n较大且k也较大时，可以避免大量无效的递归调用，从而提升算法的执行效率。

#include <vector>
using std::vector;

class TreeNode {
    // 树节点定义省略，与题目描述一致
};

class Solution {
private:
    vector<vector<int>> result; // 存放所有符合条件的组合
    vector<int> path; // 当前的组合路径
    void backtracking(int n, int k, int startIndex) {
        // 如果当前路径的长度已经满足k，将其加入到结果集中
        if (path.size() == k) {
            result.push_back(path);
            return;
        }

        // 优化的核心逻辑：剪枝
        // 还需要的元素数量为 k - path.size()
        // 因此，[startIndex, n] 中至少应有 k - path.size() 个元素
        // 即 startIndex 最大为 n - (k - path.size()) + 1
        for (int i = startIndex; i <= n - (k - path.size()) + 1; 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;
    }
};

python

初始化一个空的result列表来存储所有符合条件的组合，以及一个空的path列表来存储当前的组合路径。

定义了一个backtracking函数，它接受一个参数startIndex，表示当前递归的起始位置。

在backtracking函数内部，首先进行剪枝操作。如果当前路径长度加上区间[startIndex, n]内所有可能的选择的数量小于k，说明即使将剩余所有选项都加入到path中，也无法满足组合长度为k的要求，因此直接返回。

如果当前路径长度已经达到k，则将path的一个副本加入到result中。

然后通过一个for循环遍历从startIndex到n的所有数字，尝试将每个数字加入到path中，并递归调用backtracking函数以探索后续的数字。每次递归调用后，通过path.pop()回溯，以撤销上一步的选择。

最后，通过调用backtracking(1)开始递归过程，并返回最终的结果result。

class Solution:
    def combine(self, n: int, k: int) -> [[int]]:
        result = []  # 存放所有符合条件的组合
        path = []  # 当前路径，即一个可能的组合
        
        def backtracking(startIndex: int):
            # 剪枝：path 长度加上区间 [startIndex, n] 的长度小于 k，不可能构建出长度为 k 的 path
            if len(path) + (n - startIndex + 1) < k:
                return
            
            # 如果当前路径的长度已经满足 k，将其加入到结果集中
            if len(path) == k:
                result.append(path[:])
                return
            
            for i in range(startIndex, n + 1):
                path.append(i)  # 处理节点
                backtracking(i + 1)  # 递归探索下一层
                path.pop()  # 回溯，撤销当前节点的处理结果

        backtracking(1)
        return result