代码随想录训练营第24天|回溯|组合

回溯介绍

回溯算法是一种通过探索所有可能的候选解来找出所有解的解题策略。 - 本质就是暴力法

如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来消除那些失败的候选解，也就是说，回溯并尝试另一种可能。回溯法非常适合解决约束满足问题，其中包括组合问题、划分问题、子集问题、排列问题和棋盘问题等。

回溯算法涉及的问题

1. 组合问题：求解所有可能的组合方式，如组合总和。
2. 排列问题：求解所有可能的排列方式，如全排列问题。
3. 子集问题：求解一个集合的所有可能子集，如子集问题。
4. 棋盘问题：如N皇后问题、解数独等，通常是在二维棋盘上的放置问题，需要满足特定约束。
5. 划分问题：将一个集合划分为几个满足特定条件的子集，如划分为和相等的子集。

实际中的应用

• 数独解题器：通过回溯法遍历所有可能的数字填充方式，直到找到合法解。
• 密码破解：在一定的约束下尝试所有可能的密码组合。
• 路径规划：在迷宫求解或图中寻找路径的问题中，尝试所有可能的路径直到找到目标。
• 游戏开发：解决如八皇后问题等经典问题，也用于游戏AI中的决策制定。

回溯算法的特点

• 递归实现：通常用递归方法实现，因为这类问题很自然地就是递归定义的。
• 试错思想：它的基本思想是从一条路往下走，如果发现当前路走不通时，则回溯返回，尝试另一条路。
• 剪枝优化：在搜索过程中，通过剪枝减少搜索空间，避免不必要的搜索。

回溯算法的关键是在于找到解空间树的遍历策略，以及如何在遍历的过程中通过剪枝来减少搜索空间，从而提高算法的效率。

回溯模板

def backtrack(路径, 选择列表):
    if 满足结束条件:
        结果.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

组合问题

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()  # 回溯，撤销处理的节点

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 - (k - len(path)) + 2):  # 优化的地方
            path.append(i)  # 处理节点
            self.backtracking(n, k, i + 1, path, result)
            path.pop()  # 回溯，撤销处理的节点