代码随想录算法训练营第23天｜回溯算法Part02
记录题目：
- 分割回文串
- 组合总和
- 组合总和 II
回溯算法是“枚举+剪枝”的经典范式，不同题型的关键在于：是否允许重复使用元素、是否存在重复元素、是否需要固定顺序。
这些因素共同决定了递归的展开方式与剪枝/去重策略，掌握其背后的结构抽象，比记住模板更重要。
给你一个字符串
s，请你将s分割成一些子串，使每个子串都是回文串。返回s所有可能的分割方案。
回溯法的关键在于划分子问题并搜索所有可能解。 本题中，每一次切割构成一层递归，切割点向后推进，直到指针切到字符串末尾，视为一种合法划分。
思路解析
- 使用回溯法，从左至右尝试所有切割方案；
- 每次尝试切一段回文串，若合法，则加入路径，继续下一层递归；
- 切割线位于索引
i，截取子串范围为[startIndex, i]； - 注意递归函数需传入
i + 1，避免重复切割相同位置。
给你一个无重复元素的整数数组
candidates和一个目标整数target，找出candidates中可以使数字和为target的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
candidates中的同一个数字可以无限制重复选取。如果至少一个数字的被选数量不同，则两种组合视为不同。
实现方式一：通过 startIndex 控制搜索范围
每层递归从当前位置开始向后枚举；
排序的作用：
提前剪枝：若
sum + candidates[i] > target，可以break提前终止；树层去重：相邻相等元素可直接跳过；
本质上是对组合空间进行“逐层展开”，避免重复枚举前面的数。
实现方式二：按值大小剪枝，无需 startIndex
使用路径末尾
path[path.length - 1]限制当前可选数字不小于上一个， 从而保持非降序组合；这是一种值域剪枝技巧，可以规避重复组合而不依赖索引；
因
candidates中数值无重复，故无需考虑值相同的树层去重。
无论采用哪种方式，都必须先对 candidates 进行升序排序，以确保剪枝和去重逻辑有效运行。
类题对比
| 题目 | 使用 startIndex |
需要排序 | 说明 |
|---|---|---|---|
| 77. 组合 | 是 | 否（不强制） | 单集合组合， 控制起点防止重复 |
| 216. 组合总和 III | 是 | 否（不强制） | 数字范围固定， 使用 startIndex 控制 |
| 17. 电话号码的字母组合 | 否 | 否（不需要） | 多集合各自独立， 分别递归 |
| 39. 组合总和 | 否（可选） | 是（必须排序） | 利用数值剪枝， 避免重复组合 |
给定一个候选人编号的集合
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的每个数字在每个组合中只能使用一次。注意：解集不能包含重复的组合。
思路解析
此题与上一题的核心区别在于：
- 每个元素只能使用一次；
candidates中可能存在重复元素，因此需要进行树层去重。
树层去重 vs 树枝去重
在解决组合问题的回溯树中，我们常说“同一树层去重，树枝不去重”。这意味着：
- 树层： 同一层中若某个值已被使用过，则跳过相同值；
- 树枝： 因为下一层递归来自不同路径，值可重复。
实现关键
对
candidates排序是去重的前提；判断去重的条件为：
if (i > startIndex && candidates[i] === candidates[i - 1]) continue;该判断仅作用于同一树层，避免出现重复组合；
注意剪枝条件：若
sum + candidates[i] > target，可立即跳出当前循环。
去重方式：used[] 与 startIndex 的比较
有些题解使用 used[] 配合如下判断：
if (i > 0 && candidates[i] === candidates[i - 1] && !used[i - 1]) continue;
这是排列类问题（如 47. 全排列 II
）中的典型用法，用于判断“树枝去重”。但在本题（组合问题）中，只要使用 startIndex 控制树层，就足以完成去重，不需要 used[]。