递归、搜索与回溯算法实战：深入理解暴搜决策树

实现方案

两种剪枝策略

1. 同一层去重：在同一个节点的所有分支中，相同的元素只能选择一次。

2. 使用标记：设置 check[] 数组标记已使用的元素，确保同一个数在单次路径中只使用一次。

完善决策树

结合上述两种策略，我们可以构建出正确的决策树结构，有效避免重复分支。

思考方式对比

本质相同，都是针对是否需要剪枝的情况作出相应处理。

关注不合法分支

• 红色剪枝条件：check[i] == true，表示同一个数只能使用一次。
• 粉色剪枝条件：nums[i] == nums[i - 1]，表示同一个节点的所有分支中，相同数只能使用一次。

问题一：非连续重复元素

如果数组中的重复元素不是连在一起的（例如 [1, 2, 1, 3, 1]），直接比较相邻元素无法判断同一层是否已选过该值。

解决办法：在递归前先对 nums 排序。排序时间复杂度 O(N log N) 相对于递归的 O(2^N) 可忽略不计，但能极大简化剪枝逻辑。

问题二：区分同层与不同层

nums[i] == nums[i - 1] 的判断范围可能过宽，容易误杀合法分支。只有当 nums[i-1] 和 nums[i] 都在同一层且都未被使用时，才需要跳过 i。

• 不同层：即使数值相等，只要 nums[i-1] 已被使用（红色剪枝生效），nums[i] 就是合法的。
• 同一层：若 check[i-1] == false，说明两者在同一层，此时若数值相等，i 应被剪枝。

改进条件：

if (i != 0 && check[i] == false && nums[i] == nums[i - 1]) {
    continue;
}

问题三：边界检查

当 i = 0 时访问 nums[i - 1] 会导致越界，需增加 i != 0 判断。

关注合法分支

另一种思路是直接判断当前分支是否合法：

1. 检查是否被使用：check[i] == false。
2. 检查是否同层重复：若 check[i-1] == false 且 nums[i] == nums[i-1]，则跳过。
3. 首元素处理：i = 0 时只需检查 check[0] == false。

代码实现

方案一：只关心不合法分支

方案二：只关心合法分支

电话号码的字母组合

题目描述

给定仅包含数字 2-9 的字符串，返回所有它能代表的字母组合。

解题思路

可以使用深度优先遍历（DFS）来模拟决策过程，在叶子节点收集结果。

实现方案

映射关系

使用字符串数组存储数字到字母的映射，下标为 2 对应 "abc"，以此类推。遍历时将字符减去 '0' 即可获取对应下标。

全局变量与函数

定义 ret 存储结果，path 存储当前路径，map 存储映射关系。

代码实现

括号生成

题目描述

给出 n 对括号，生成所有有效的括号组合。

解题思路

有效括号必须满足：遍历过程中左括号数量始终大于等于右括号数量，且最终左右括号数量相等。

实现方案

决策树与剪枝

• 蓝色剪枝：左括号数量超过 n。
• 紫色剪枝：右括号数量超过左括号数量。

变量设计

可以将变量设为全局变量或通过参数传递，区别在于恢复现场的方式不同。

代码实现

组合

题目描述

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

解题思路

组合不考虑顺序，只考虑元素种类。可以通过控制递归起点来避免重复组合。

实现方案

决策树规律

观察发现，为了避免重复（如 [1,2] 和 [2,1]），向下递归时应从当前元素的下一个位置开始。

代码实现

目标和

题目描述

给一个非负整数数组和一个目标值 target，在每个数字前添加 + 或 -，使表达式结果等于 target。

解题思路

每个数字都有正负两种选择，构成一棵二叉决策树，通过 DFS 遍历所有路径。

实现方案

代码实现对比

全局变量 path（手动回溯）

参数 path（自动回溯）

注意：如果提前修改了 path 的状态（如 path += nums[i]），编译器在恢复现场时只会恢复参数值，而 path 作为引用类型无法自动回退，导致错误。

组合总和

题目描述

给定无重复元素的候选数组 candidates 和目标数 target，找出所有唯一组合使得数字之和为 target。

解题思路

允许重复选取同一数字，属于有放回的组合问题。

实现方案

解法一：标准回溯

• 红色剪枝：超过 target 的分支。
• 紫色剪枝：避免重复组合。

规律：有效递归都是从当前节点开始向后枚举，下一轮递归传入当前索引即可。

常见错误：未处理 pos 越界，或未正确处理重复元素的选择。

解法二：循环枚举次数

每一层枚举当前数字使用的次数，直到超过 target。

细节处理：

1. 恢复时机：必须在枚举完某个数字的所有可能次数后，统一恢复现场。
2. sum 与 path：sum 随参数传递自动恢复，path 需手动移除元素。
3. 循环起点：恢复现场时从 k=1 开始，因为 k=0 时并未实际添加元素。

字母大小写全排列

题目描述

给定一个字符串 s，通过转换字母的大小写生成所有可能的排列。

解题思路

每个字母有两种状态（大写或小写），数字保持不变。本质上是一个二叉树遍历问题。

实现方案

决策树

可以在原字符串上操作，或者维护一个全局 path。遇到字母时进行分支选择，遇到数字直接追加。

代码实现