LeetCode 39. 组合总和

题目描述给定一个无重复元素的整数数组candidates和一个目标整数target找出candidates中可以使数字和为target的所有不同组合。答案可以按任意顺序返回。candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同则两种组合是不同的。例如输入candidates [2,3,6,7], target 7 输出[[2,2,3],[7]]初始思路这题可以使用“选或不选”的回溯模型。定义递归函数dfs(candidates, target, path, i)含义是当前正在考虑candidates[i]在还需要凑出target的情况下继续搜索所有可能组合。每一层有两个选择1. 选当前数字 candidates[i] 2. 跳过当前数字 candidates[i]因为题目允许同一个数字重复选择所以选了candidates[i]之后下一层仍然可以继续考虑candidates[i]。也就是选当前数字dfs(i) 不选当前数字dfs(i 1)解题思路这题和普通子集问题很像但多了一个关键条件同一个数字可以无限制重复被选取。所以当我们选择当前数字后不能直接进入i 1而是继续停留在i。以candidates [2,3,6,7]target 7为例当前考虑 2 选 2 - target 变成 5仍然可以继续选 2 不选 2 - 去考虑 3递归过程可以理解为1. 如果 target 0说明当前 path 的和刚好等于目标值加入答案 2. 如果 target 0说明当前路径已经超过目标值停止 3. 如果 i 越界说明没有数字可以继续考虑停止 4. 选择 candidates[i]递归 dfs(i) 5. 撤销选择递归 dfs(i 1)这里的“撤销选择”非常重要因为path是同一个列表对象选当前数字的分支结束后要恢复现场才能进入“不选当前数字”的分支。代码实现class Solution { ListListInteger ans; public ListListInteger combinationSum(int[] candidates, int target) { ans new ArrayList(); ListInteger path new ArrayList(); dfs(candidates, target, path, 0); return ans; } public void dfs(int[] candidates, int target, ListInteger path, int i) { if (target 0) { ans.add(new ArrayList(path)); return; } if (target 0 || i candidates.length) { return; } path.add(candidates[i]); dfs(candidates, target - candidates[i], path, i); path.remove(path.size() - 1); dfs(candidates, target, path, i 1); } }为什么选了还递归 i这是本题和普通“选或不选”子集题最关键的区别。普通子集问题中每个元素只能使用一次选 nums[i] 后下一层处理 i 1但这题允许重复使用当前数字选 candidates[i] 后下一层仍然处理 i比如目标是7当前数字是2选一次 2 后 target 5 还可以继续选 2 再选一次 2 后 target 3 还可以继续选 2 或跳过 2 去选 3所以递归写成dfs(candidates, target - candidates[i], path, i);而不是dfs(candidates, target - candidates[i], path, i 1);为什么不会产生重复组合这份写法中i只会保持不变或向右移动选当前数i 不变 跳过当前数i 1因此组合中的数字顺序不会回头。比如已经跳过了2进入3后就不会再回头选择2。这样可以避免生成[2,3,2]这类和[2,2,3]本质相同但顺序不同的重复组合。易错点1. dfs 的含义不能写成“把 candidates[i] 加入 path”dfs(i, target)的含义应该是当前考虑 candidates[i]还需要凑出 target“加入当前数”只是其中一个分支不是递归函数本身的含义。2. 选当前数后不能直接 i 1因为同一个数字可以重复选所以选了candidates[i]后下一层还是从i开始。只有在“不选当前数”时才进入i 1。3. 加入答案时要拷贝 path不能直接写ans.add(path);因为path后续还会继续被回溯修改。正确写法是ans.add(new ArrayList(path));4. 回溯后要恢复 path选择当前数字后path.add(candidates[i]);递归结束后要撤销path.remove(path.size() - 1);这样“不选当前数字”的分支才不会受到影响。5. 终止条件要覆盖 target 和 i当target 0时说明找到一个合法组合。当target 0或i candidates.length时说明当前路径不可能继续得到合法答案需要返回。复杂度分析设n candidates.lengthtarget为目标值min为数组中的最小值。递归深度最多约为target / min因为每次选择一个数后target至少会减少min。时间复杂度与最终搜索树规模有关常见估计为指数级。可以粗略理解为O(2^(target / min))量级。空间复杂度O(target / min)主要来自递归栈和path。如果把返回结果也计入空间还要加上所有组合占用的空间。复盘这题的核心不是简单套全排列或子集模板而是先判断当前层的选择模型。对于 39 题最清楚的模型是当前数字选不选如果选因为可以重复使用所以继续停留在当前下标i。如果不选说明当前数字以后都不再考虑进入i 1。只要能想清楚这两个分支代码里的递归方向就不会写乱。Tips组合总和可以记住一句话选当前数继续 dfs(i)跳过当前数dfs(i 1)。这里的i控制候选数字范围target控制还差多少path记录当前已经选择的组合。