今日任务：

1. 回溯理论基础
2. LeetCode77 组合

资料来源

1. 代码随想录 | 回溯理论基础
2. 代码随想录 | LeetCode77 组合

1 回溯理论基础

回溯法，也叫回溯搜索法，是一种用于搜索符合条件的情况的使用递归的通用算法思路。它的本质就是暴力搜索，因此它的效率并不高，但是有些问题是本来就没有什么有效的算法，能出结果就算成功，回溯属于是矬子里拔大个，能提升它的效率的方法只有进行适当的剪枝操作。回溯算法能解决的问题如下：

1. 组合问题：n个数字中，找出符合一定规则的k个数字的组合。
2. 切割问题：一个字符串中，按一定的规则能够有多少切法。
3. 子集问题：n个数字中，找出符合一定规则的子集。
4. 排列问题：n个数字中，按一定规则进行排列，有多少种排列方式。
5. 棋盘问题：N皇后问题，数独问题。

因为回溯问题都是用递归来解决的，所有所有回溯问题都可以被抽象为树形结构，要查找的集合的大小就构成了树的宽度，递归的深度就构成了树的深度。有递归就要有终止条件，所以这棵树必然是一棵高度有限的n叉树。

相比递归问题的三要素，回溯问题的模板就多了一个回溯的过程：

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

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

2 LeetCode77 组合

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

输入：n = 1, k = 1
输出：[[1]]

这道题就是经典的暴力行不通只能回溯的情况。如果是要暴力循环去做的话，for循环的层数必须要与k相同，这就不可能行得通。而回溯可以通过在递归中进行循环的方式来做。

python
from typing import List

class Solution:
    def __init__(self):
        self.path = []
        self.result = []

    def combine(self, n: int, k: int) -> List[List[int]]:
        self.back_tracking(n, k, 1)
        return self.result

    def back_tracking(self, n: int, k: int, start_index: int):
        if len(self.path) == k:  # 满足条件 终止递归
            self.result.append(self.path.copy())
            return
        for i in range(start_index, n + 1):  # 单层递归的逻辑
            self.path.append(i)
            self.back_tracking(n, k, i + 1)
            self.path.pop()
        return

这道题也可以进行适当的剪枝操作。一种情况是k为1的时候，那就没什么必要再去递归了，直接生成结果就行了。另外还有k足够大的时候，有些递归的情况里，递归到最后result都不够长，因此注定不会有结果。这部分也可以进行剪枝。剪枝后的代码如下：

python
from typing import List

class Solution:
    def __init__(self):
        self.path = []
        self.result = []

    def combine(self, n: int, k: int) -> List[List[int]]:
        if k == 1:
            return [[i] for i in list(range(1, n + 1))]
        self.back_tracking(n, k, 1)
        return self.result

    def back_tracking(self, n: int, k: int, start_index: int):
        if len(self.path) == k:  # 满足条件 终止递归
            self.result.append(self.path.copy())
            return
        for i in range(start_index, (n + 1) - (k - len(self.path)) + 1):  # 剪枝操作
            self.path.append(i)
            self.back_tracking(n, k, i + 1)
            self.path.pop()
        return

剪枝思路：

1. 当前递归中，已经进去的元素有len(self.path)个。
2. 还需要k - len(self.path)个。
3. 在集合中，遍历终点是(n + 1) - (k - len(self.path)) + 1)，如果超过这个终点在继续遍历下去，之后递归到底时的path都不会够k个元素。