本题采用回溯搜索结合排序剪枝算法又称“无限制重复路径搜索法”或“动态减枝递归法”解决无重复元素数组中数字和为目标值的组合求解问题。其核心本质是将一维数组转换为一棵决策树通过控制递归起始下标消除重复组合并利用有序数组的单调递增性提前拦截越界分支。当前提供的源码实现了对状态空间的深度优先剪枝最终走向是精准输出所有满足数字和为目标值的唯一组合列表。一、 问题本质与数据模型对于给定的无重复元素整数数组 candidates 和目标值 target题目要求找出所有和为 target 的不同组合。该问题面临两个核心物理约束无限制重复选取约束candidates 中的同一个数字可以无限制重复被选取只要其累加和不超过 target。组合唯一性约束结果集不得包含重复的组合。例如[2, 2, 3]与[2, 3, 2]被视为同一种组合只能保留一个。如果采用常规的无差别排列回溯将会导致搜索空间极度膨胀且产生大量重复组合例如对于输入[2, 3]和 target 为 5会产生[2, 3]和[3, 2]两种状态。为了破除这种拓扑非对称困局算法引入了“有序去重与单调剪枝模型”。首先通过Arrays.sort(candidates)对输入数组进行升序排列。在递归搜索中我们维护一个当前的递归起始索引i。在当前层进行分支选择时循环变量j从i开始递增在向下压栈递归时传递的起始索引更新为j。这种“不回头”的选择机制强行限制了生成路径的非递减性例如在选择了 3 之后由于递归起点变为了 3 对应的索引后续分支只能选择 3 及其右侧的元素绝不可能回头选择 2。从而在搜索源头上物理消除了生成[3, 2]的可能完美保证了组合的唯一性。此外由于数组已被物理排序如果在循环中当前元素candidates[j]已经严格大于剩余目标值remain由于数组的单调递增性该元素右侧的所有后继元素也必然大于remain。因此无需继续向下探测可直接在该处截断循环实现强力剪枝。二、 算法演进对比在解决组合总和问题时回溯法结合排序剪枝在时空资源的控制上表现优异解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷无剪枝暴力回溯O(N 的 M 次幂)O(M)每次从头遍历 candidates 寻找所有排列最后通过 Set 集合去重产生了大量的重复排列和无效搜索路径时空开销极大仅带去重回溯O(N 的 M 次幂)O(M)通过控制递归起始索引i保证组合唯一但循环内不进行大小判定即使当前元素已超越 target循环仍会强行遍历完整个数组产生无效压栈排序并剪枝回溯当前解法O(S * N)O(M)数组排序后控制递归起点去重并在循环条件中融入candidates[j] remain拦截无效分支依赖输入的可排序性但剪枝效率达到空间搜索的极限注N为 candidates 数组的长度。M为最大递归深度在极端情况下全部选最小元素M target / min(candidates)。S为合法的搜索状态和解的总数根据提示本题保证解的个数少于 150 个因此实际运行效率极高。三、 核心分支控制逻辑与决策证明当前源码的控制流完全依赖于dfs递归函数内的目标和检测与for循环中的剪枝防护网其内部决策分支证明如下1. 目标命中分支if (remain 0)执行ans.add(new ArrayList(path))并直接返回。物理意义剩余目标值remain精确归零说明当前的路径容器path中的数值累加和完美契合target。此时必须对path进行一次物理深拷贝Deep Copy并注入全局结果集随后退出当前分支。2. 同一数字重复选取控制dfs(ans, path, candidates, remain - candidates[j], j)执行在下一层递归中传入的起始索引仍为j。数学证明传入j而不是j 1允许下一层递归继续从当前的candidates[j]节点出发进行决策完美对应了题目中“同一个数字可以无限制重复被选取”的约束。3. 剪枝决策拦截candidates[j] remain执行将其作为for循环的终止条件之一j candidates.length candidates[j] remain。数学证明设排序后的数组在索引j处满足candidates[j] remain。由于数组是有序的对于任意的k j显然有candidates[k] candidates[j] remain。这意味着从位置j开始往右的所有元素减去后剩余的值必然小于 0。结论后续所有分支都不可能产生合法解。此时直接终止循环而不是仅仅continue将当前层级的后半段搜索空间物理截断实现 O(1) 级别的整株子树剪枝。四、 算法执行状态机步进示例以输入candidates [2, 3, 6, 7]已是有序target 7为例展示回溯状态机在遭遇剪枝、命中和回溯时的步进过程步骤当前递归层级深度当前剩余目标 remain循环变量 j (对应数值)动作类型与判定条件路径容器 path 的物理状态初始170 (数值: 2)选 2进入下一层递归[2]1250 (数值: 2)选 2进入下一层递归[2, 2]2330 (数值: 2)选 2进入下一层递归[2, 2, 2]3410 (数值: 2)2 1循环条件失败触发剪枝触发回溯弹出末尾 2回退至[2, 2]4331 (数值: 3)3 3 成立选 3[2, 2, 3]540-remain 0命中目标拷贝[2, 2, 3]存入答案弹出 3回退至[2, 2]6332 (数值: 6)6 3循环条件失败触发剪枝终止本层循环弹出 2回退至[2]7251 (数值: 3)3 5 成立选 3[2, 3]8321 (数值: 3)3 2循环条件失败触发剪枝终止本层循环弹出 3回退至[2]9252 (数值: 6)6 5循环条件失败触发剪枝终止本层循环弹出 2回退至[]10173 (数值: 7)7 7 成立选 7[7]1120-remain 0命中目标拷贝[7]存入答案弹出 7回退至[]遍历结束五、 源码实现import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Solution { public ListListInteger combinationSum(int[] candidates, int target) { // 核心控制先对数组执行升序排序为后续的单调性剪枝策略提供物理基础 Arrays.sort(candidates); ListListInteger ans new ArrayList(); ListInteger path new ArrayList(); // 启动深度优先搜索回溯状态机 dfs(ans, path, candidates, target, 0); return ans; } private void dfs(ListListInteger ans, ListInteger path, int[] candidates, int remain, int i) { // 基准收敛条件若剩余目标值精准减至 0说明找到合法组合执行深拷贝入库 if (remain 0) { ans.add(new ArrayList(path)); return; } // 剪枝控制核心j 从 i 开始防止回头选择产生重复组合 // 循环条件 candidates[j] remain 是核心剪枝防护网一旦不成立直接截断整层循环 for (int j i; j candidates.length candidates[j] remain; j) { // 状态置位将当前候选数值压入路径容器 path.add(candidates[j]); // 向下递归剩余目标减少且递归起点传入 j支持当前元素无限制重复选取 dfs(ans, path, candidates, remain - candidates[j], j); // 状态复位回溯将末尾元素弹出清理物理现场供同层后继分支使用 path.removeLast(); } } }六、 复杂度分析1. 时间复杂度O(S * N)分析从回溯树的全局来看算法的最坏时间复杂度是指数级的。设 N 为 candidates 的长度M 为最大树高。但在引入了candidates[j] remain的剪枝策略后实际被检索到的无效状态数被极大地压缩。由于题目约束“解的组合个数少于 150 个”意味着回溯树中实际可到达的叶子节点即remain 0状态是非常稀疏的。在每个有效状态上回溯及结果拷贝操作的开销与当前path长度呈正比最大为 M。结论算法的时间开销完全由最终的合法解总数与剪枝后的状态树节点数决定实际运行效率远超未经剪枝的暴力搜索定性为 O(S * N)其中 S 为搜索状态的实际收敛规模。2. 空间复杂度O(M)分析算法的空间开销来自于两部分一是递归方法调用栈的物理深度二是临时存储路径的path列表。由于每一次递归至少消耗 candidates 中的最小元素min的大小因此递归的最大深度被限制在M target / min级别。在本题中target 最大为 40候选数值最小为 2故最大树高 M 严格不大于 20。结论除了用于存储最终结果的ans列表外算法的动态辅助栈内存消耗为 O(M)完全属于常数阶范围内的超轻量级内存开销。