代码随想录算法训练营第二十四天 | 77. 组合

回溯算法理论基础

https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

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

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

回溯法并不是什么高效的算法 =>本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

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

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

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

  回溯三部曲

  • 回溯函数模板返回值以及参数 - backtracking
  • 回溯函数终止条件 - 搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归

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

  • 回溯搜索的遍历过程 - 集合的大小构成了树的宽度，递归的深度构成的树的深度。

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

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

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

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

    ![[Pasted image 20240301152922.png]]

    完整模板：

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

    77.组合

    https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html

    class Solution:
        def combine(self, n: int, k: int) -> List[List[int]]:
            result = []
            self.backtracking(n,k,1,[],result)
            return result
        def backtracking(self, n, k, startIndex, path, result):
            if len(path) == k:
                result.append(path[:])
                return
            for i in range(startIndex, n+1):
                path.append(i)
                self.backtracking(n,k,i+1,path,result)
                path.pop()