第7章：回溯与剪枝

章节大纲

7.1 回溯模板：选择、探索、撤销

回溯算法的本质：系统化的试错
三要素模板：选择列表、路径记录、结束条件
经典例题：全排列、组合总和

7.2 排列组合子集问题

排列：顺序重要的选择
组合：顺序无关的选择
子集：包含空集的所有可能
去重技巧：排序+跳过重复

7.3 N皇后与数独：约束满足

约束传播与回溯的结合
位运算优化状态表示
启发式搜索：最受限变量优先

7.4 剪枝技巧：可行性与最优性剪枝

可行性剪枝：提前判断无解
最优性剪枝：基于当前最优解
对称性剪枝：利用问题对称性

本章小结

常见陷阱与错误

开篇：搜索空间的系统探索

回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来丢弃该解，即"回溯"并且再次尝试。

对于有函数式编程背景的工程师来说，回溯可以理解为一种带有副作用管理的深度优先搜索。每次递归调用相当于在搜索树中向下走一步，而回溯则是返回上一层并恢复状态。这种"尝试-失败-撤销"的模式，本质上是在隐式地构建和遍历一棵解空间树。

从代数角度看，回溯问题通常可以表示为在约束条件下寻找满足特定性质的向量或矩阵。例如，N皇后问题可以看作寻找一个置换矩阵，使得任意两个1不在同一对角线上。这种视角有助于我们设计更高效的剪枝策略。

本章将系统介绍回溯算法的核心思想和实现技巧，重点关注如何通过剪枝优化搜索效率。我们将从基础的回溯模板开始，逐步深入到复杂的约束满足问题，最后探讨各种剪枝技巧的应用。

7.1 回溯模板：选择、探索、撤销

回溯算法的本质

回溯算法的核心是一个递归函数，它在每一步都面临若干选择，需要：

做出选择：从候选集中选择一个元素
递归探索：基于当前选择继续搜索
撤销选择：回到选择前的状态，尝试其他可能

这个过程可以用以下伪代码表示：

def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 新的选择列表)
        撤销选择

从函数式编程的角度，回溯是一种特殊的折叠（fold）操作，我们在遍历搜索树的同时累积所有满足条件的解。关键在于如何高效地管理状态的保存和恢复。

经典例题1：全排列 (LeetCode 46)

全排列是回溯算法最经典的应用。给定不含重复数字的数组，返回所有可能的排列。

def permute(nums):
    result = []

    def backtrack(path, remaining):
        # 结束条件：所有数字都被选择
        if not remaining:
            result.append(path[:])  # 注意要复制path
            return

        # 遍历所有可选择的数字
        for i in range(len(remaining)):
            # 做选择
            num = remaining[i]
            path.append(num)

            # 递归：继续选择剩余的数字
            backtrack(path, remaining[:i] + remaining[i+1:])

            # 撤销选择
            path.pop()

    backtrack([], nums)
    return result

优化版本：使用visited数组避免创建新列表

def permute_optimized(nums):
    result = []
    n = len(nums)

    def backtrack(path, visited):
        if len(path) == n:
            result.append(path[:])
            return

        for i in range(n):
            if visited[i]:
                continue

            # 做选择
            path.append(nums[i])
            visited[i] = True

            # 递归
            backtrack(path, visited)

            # 撤销选择
            path.pop()
            visited[i] = False

    backtrack([], [False] * n)
    return result

经典例题2：组合总和III (LeetCode 216)

找出所有相加之和为n的k个数的组合，只使用数字1到9，每个数字最多使用一次。

def combinationSum3(k, n):
    result = []

    def backtrack(start, path, target):
        # 剪枝：路径长度超过k或目标值为负
        if len(path) > k or target < 0:
            return

        # 结束条件
        if len(path) == k and target == 0:
            result.append(path[:])
            return

        # 从start开始避免重复组合
        for i in range(start, 10):
            # 剪枝：当前数字已经大于剩余目标
            if i > target:
                break

            path.append(i)
            backtrack(i + 1, path, target - i)
            path.pop()

    backtrack(1, [], n)
    return result

回溯的时间复杂度分析

回溯算法的时间复杂度通常是指数级的，因为它需要遍历整个解空间树。具体复杂度取决于：

分支因子b：每个节点的平均分支数
树的深度d：递归的最大深度
剪枝效果：有效的剪枝可以大幅减少搜索空间

一般情况下，时间复杂度为 $O(b^d)$。例如：

全排列：$O(n! \times n)$，其中n!是排列数，n是构造每个排列的时间
k个数的组合：$O(C_n^k \times k)$，其中$C_n^k$是组合数

状态管理技巧

原地修改vs创建副本： - 原地修改效率高，但需要显式撤销 - 创建副本代码简洁，但空间开销大
使用位掩码表示状态（适用于n≤32的情况）：

def permute_bitmask(nums):
    n = len(nums)
    result = []

    def backtrack(path, used):
        if len(path) == n:
            result.append(path[:])
            return

        for i in range(n):
            if used & (1 << i):
                continue

            path.append(nums[i])
            backtrack(path, used | (1 << i))
            path.pop()

    backtrack([], 0)
    return result

7.2 排列组合子集问题

排列、组合和子集是回溯算法的三大经典应用场景。理解它们之间的区别和联系，是掌握回溯算法的关键。

问题的本质区别

从数学角度看：

排列（Permutation）：n个不同元素的全排列数为 $n!$
组合（Combination）：从n个元素中选k个的组合数为 $C_n^k = \frac{n!}{k!(n-k)!}$
子集（Subset）：n个元素的所有子集数为 $2^n$

从实现角度看，关键区别在于：

排列关心顺序，[1,2]和[2,1]是不同的排列
组合不关心顺序，[1,2]和[2,1]是同一个组合
子集是所有可能的组合（包括空集）

子集问题 (LeetCode 78, 90)

基础版：不含重复元素的子集

def subsets(nums):
    result = []

    def backtrack(start, path):
        # 子集问题的特点：每个状态都是一个有效答案
        result.append(path[:])

        for i in range(start, len(nums)):
            path.append(nums[i])
            # 关键：下一层从i+1开始，避免重复
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

进阶版：含重复元素的子集II

def subsetsWithDup(nums):
    nums.sort()  # 排序是去重的关键
    result = []

    def backtrack(start, path):
        result.append(path[:])

        for i in range(start, len(nums)):
            # 去重的核心逻辑
            if i > start and nums[i] == nums[i-1]:
                continue

            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

去重原理：当我们在同一层递归中遇到相同的元素时，只选择第一个。这确保了相同元素在结果中的相对位置固定，从而避免重复。

全排列II：含重复数字 (LeetCode 47)

def permuteUnique(nums):
    nums.sort()
    result = []
    n = len(nums)

    def backtrack(path, visited):
        if len(path) == n:
            result.append(path[:])
            return

        for i in range(n):
            # 已访问的跳过
            if visited[i]:
                continue

            # 去重：相同数字必须按照原始顺序使用
            if i > 0 and nums[i] == nums[i-1] and not visited[i-1]:
                continue

            path.append(nums[i])
            visited[i] = True
            backtrack(path, visited)
            path.pop()
            visited[i] = False

    backtrack([], [False] * n)
    return result

递增子序列 (LeetCode 491)

这是一个特殊的子集问题，要求保持原数组顺序且递增，不能排序。

def findSubsequences(nums):
    result = []

    def backtrack(start, path):
        if len(path) >= 2:
            result.append(path[:])

        # 用集合记录本层使用过的数字
        used = set()

        for i in range(start, len(nums)):
            # 不满足递增条件
            if path and nums[i] < path[-1]:
                continue

            # 本层去重
            if nums[i] in used:
                continue

            used.add(nums[i])
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

组合问题的变体

组合总和 (LeetCode 39)：可重复使用元素

def combinationSum(candidates, target):
    result = []

    def backtrack(start, path, remain):
        if remain == 0:
            result.append(path[:])
            return

        if remain < 0:
            return

        for i in range(start, len(candidates)):
            path.append(candidates[i])
            # 注意：传入i而不是i+1，允许重复使用
            backtrack(i, path, remain - candidates[i])
            path.pop()

    backtrack(0, [], target)
    return result

组合总和II (LeetCode 40)：不可重复使用

def combinationSum2(candidates, target):
    candidates.sort()
    result = []

    def backtrack(start, path, remain):
        if remain == 0:
            result.append(path[:])
            return

        for i in range(start, len(candidates)):
            # 剪枝：后续元素更大，不可能满足
            if candidates[i] > remain:
                break

            # 去重
            if i > start and candidates[i] == candidates[i-1]:
                continue

            path.append(candidates[i])
            backtrack(i + 1, path, remain - candidates[i])
            path.pop()

    backtrack(0, [], target)
    return result

统一框架与模式识别

所有排列组合子集问题都可以用以下框架解决：

def general_backtrack(nums, k=None, target=None, allow_dup=False):
    result = []

    def backtrack(start_or_visited, path, ...):
        # 终止条件（根据问题类型）
        if 满足条件:
            result.append(path[:])
            return

        # 遍历选择
        for i in 选择范围:
            # 剪枝条件
            if 不满足约束:
                continue

            # 去重逻辑（如果需要）
            if 需要去重 and 是重复选择:
                continue

            # 做选择
            更新path和其他状态

            # 递归
            backtrack(新的参数)

            # 撤销选择
            恢复path和其他状态

    backtrack(初始参数)
    return result

识别要点：

是否关心顺序：排列用visited数组，组合/子集用start索引
是否有重复元素：需要排序+去重逻辑
是否可重复使用：影响递归时的起始位置
是否有额外约束：如目标和、递增等