回溯算法是一种系统地搜索问题所有可能解的算法，适用于组合、排列、子集等问题。其通用公式一般可以用递归框架表示，以下是标准的回溯算法框架：

回溯算法通用框架

def backtrack(状态, 选择列表):
    if 终止条件(状态):
        记录结果
        return
    
    for 选择 in 选择列表:  # 遍历所有可能的选择
        if 剪枝条件(选择):  # 剪枝，跳过不符合要求的情况（可选）
            continue
        
        做出选择(更新状态)
        backtrack(新的状态, 剩余的选择)
        撤销选择(恢复状态)  # 回溯，撤销刚才的选择

回溯三要素

  1. 选择列表（Candidates）：可以做的所有选择，通常是数组、字符串的子集或排列等。

  2. 递归终止条件（Base Case）：满足条件时，保存结果并返回。

  3. 状态恢复（Backtracking）：在递归返回后，需要撤销之前的选择，以便尝试下一个可能的选择。

通用回溯算法步骤

  1. 定义递归函数

  2. 判断终止条件

  3. 循环遍历所有可能选择

  4. 做出选择

  5. 递归调用

  6. 撤销选择（回溯）

常见回溯问题示例

1. 组合问题

给定 n 个数字，求所有 k 个数字的组合。

def combine(n, k):
    res = []

    def backtrack(start, path):
        if len(path) == k:  # 终止条件
            res.append(path[:])
            return
        
        for i in range(start, n + 1):
            path.append(i)  # 做选择
            backtrack(i + 1, path)  # 递归
            path.pop()  # 回溯，撤销选择
    
    backtrack(1, [])
    return res

2. 子集问题

求一个集合的所有子集：

def subsets(nums):
    res = []

    def backtrack(start, path):
        res.append(path[:])  # 终止条件，任何时刻都可以加入子集
        
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()  # 撤销选择
    
    backtrack(0, [])
    return res

3. 全排列

def permute(nums):
    res = []
    used = [False] * len(nums)

    def backtrack(path):
        if len(path) == len(nums):  # 终止条件
            res.append(path[:])
            return
        
        for i in range(len(nums)):
            if used[i]:  # 跳过已使用的数字
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()  # 回溯
            used[i] = False
    
    backtrack([])
    return res

回溯算法核心思想

  • 穷举所有可能的解，但不会直接暴力搜索，而是利用 剪枝 和 回溯 来减少不必要的计算。

  • 递归+回溯 实现搜索，遇到无解的情况就 撤销选择 并尝试新的路径。

  • 适用于组合、子集、排列、数独求解、图算法（如 DFS）等问题。

总结

回溯算法的通用模板：

def backtrack(状态, 选择列表):
    if 终止条件(状态):
        记录结果
        return
    
    for 选择 in 选择列表:
        if 剪枝条件(选择):  
            continue
        
        做出选择(更新状态)
        backtrack(新的状态, 剩余的选择)
        撤销选择(恢复状态)