Hot 100 --- 组合总和

本文概览本文以LeetCode题目组合总和为例讲解回溯法在可重复选择、结果不计顺序场景下的应用以及和子集问题的对比一、题目二、题目分析题目要求给定一个无重复元素的正整数数组 candidates 和一个目标数 target找出 candidates 中所有可以使数字和为 target 的组合。同一个数字可以被无限制重复选取但结果集不能包含重复的组合[1,2] 和 [2,1] 算重复比如 candidates [2, 3, 6, 7]target 7输出[[2, 2, 3], [7]][2, 2, 3]2 被选了两次加起来 7[7]直接选一个 7这题一开始容易想到先排序用前缀和但这里行不通前缀和的前提是结果必须是原数组的连续子数组但本题的组合可以从任意位置选甚至可以重复选本题的组合可以重复选取同一个元素前缀和只能每个元素用一次所以本题的正确思路是回溯——遍历所有可能的选择路径和子集问题的对比子集组合总和每个元素能选几次最多 1 次无限次结果所有子集和 target 的组合终止条件遍历完所有元素sum target 或 sum target递归参数start下次从 start1 开始start下次从start含自己开始核心区别子集递归时传i 1不能再选自己组合总和递归时传i可以继续选自己思路概览classSolution{privatefinalListListIntegerresultnewArrayList();privatefinalListIntegerpathnewArrayList();privateintsum0;publicListListIntegercombinationSum(int[]candidates,inttarget){if(candidatesnull||candidates.length0){returnnewArrayList();}backtrack(candidates,target,0);returnresult;}privatevoidbacktrack(int[]candidates,inttarget,intstart){if(sumtarget){result.add(newArrayList(path));return;}if(sumtarget){return;}for(intistart;icandidates.length;i){path.add(candidates[i]);sumcandidates[i];backtrack(candidates,target,i);sum-candidates[i];path.removeLast();}}}思路简要说明两个终止条件sum target时收集结果sum target时剪枝返回start 参数控制只往后选避免 [2,3] 和 [3,2] 重复递归传 i 不是 i1允许重复选择当前元素三、思路详解第一步为什么不能用前缀和看到数组求和 target很多人第一反应是排序 前缀和。但仔细看题目问题一结果不是连续子数组前缀和解决的是从原数组中找一段连续的子数组但本题的组合可以从任意位置挑比如 candidates [2, 3, 6, 7] 中挑 [2, 2, 3]2 用了两次位置也不连续问题二可以重复选择前缀和的每个元素只被计算一次本题允许一个元素被选无数次前缀和天然做不到所以只能回溯——枚举所有可能的选择路径第二步为什么用 start 参数如果不控制顺序[2, 3] 和 [3, 2] 会被算成两个组合题目视为重复。解决办法是规定只往后选——每次选完一个元素后下次选择只能从当前位置开始往后以 candidates [2, 3, 6, 7]target 7 为例选 2i0后下次只能从 i0 开始含 2 自己即 {2, 3, 6, 7} 选 2i0后下次还是从 i0 开始 选 2 → sum6继续 ... 选 3i1后下次从 i1 开始含 3即 {3, 6, 7} 不能回头选 2否则会出现 [2, 3, 2] 和 [2, 2, 3] 重复这样保证每个组合的元素只按数组下标非递减顺序排列天然去重第三步递归传 i 而不是 i1这是和子集问题最大的区别// 子集每个元素最多选 1 次backtrack(res,i1,nums,subset);// 组合总和可以重复选择backtrack(candidates,target,i);传i意味着下次可以再选自己实现了元素的重复选择。以 candidates [2, 3, 6, 7]选到 2 之后第一次选 2 → path[2] 递归传 i0下次仍可以选 2 第二次选 2 → path[2, 2] 递归传 i0下次仍可以选 2 第三次选 2 → path[2, 2, 2]sum6 7 ...第四步两个终止条件if(sumtarget){result.add(newArrayList(path));return;}if(sumtarget){return;}sum target找到一个合法组合收集后返回sum target当前路径已经超出目标继续往下加只会更大直接剪枝返回因为 candidates 都是正数sum 只会越加越大所以超过就没必要继续第五步回溯操作for 循环内的四行代码是回溯的核心path.add(candidates[i]);// 选加入路径sumcandidates[i];// 选更新总和backtrack(candidates,target,i);// 往下递归sum-candidates[i];// 撤销恢复总和path.removeLast();// 撤销移除路径最后一个选就是 add sum撤销就是 sum- removeLast。每次选完往深处走回来后完整撤销for 循环 i 换下一个元素第六步完整执行过程以 candidates [2, 3, 6, 7]target 7 为例backtrack(start0, path[], sum0) ├── 选 2 → path[2], sum2 │ └── backtrack(start0) │ ├── 选 2 → path[2,2], sum4 │ │ └── backtrack(start0) │ │ ├── 选 2 → path[2,2,2], sum6 │ │ │ └── backtrack(start0) │ │ │ ├── 选 2 → sum8 7剪枝 │ │ │ ├── 选 3 → sum9 7剪枝 │ │ │ ├── 选 6 → sum12 7剪枝 │ │ │ └── 选 7 → sum13 7剪枝 │ │ ├── 选 3 → path[2,2,3], sum7 ✓ 收集 [2,2,3] │ │ ├── 选 6 → sum10 7剪枝 │ │ └── 选 7 → sum11 7剪枝 │ ├── 选 3 → path[2,3], sum5 │ │ └── backtrack(start1) │ │ ├── 选 3 → sum8 7剪枝 │ │ ├── 选 6 → sum11 7剪枝 │ │ └── 选 7 → sum12 7剪枝 │ ├── 选 6 → sum8 7剪枝 │ └── 选 7 → sum9 7剪枝 ├── 选 3 → path[3], sum3 │ └── backtrack(start1) │ ├── 选 3 → path[3,3], sum6 │ │ └── 后面都超剪枝 │ ├── 选 6 → sum9剪枝 │ └── 选 7 → sum10剪枝 ├── 选 6 → path[6], sum6 │ └── backtrack(start2) │ ├── 选 6 → sum12剪枝 │ └── 选 7 → sum13剪枝 └── 选 7 → path[7], sum7 ✓ 收集 [7]最终结果[[2, 2, 3], [7]]第七步和之前几道题的对比全排列子集方法二电话号码组合总和顺序关心不关心关心不关心元素能选几次1 次1 次选/不选1 次多选一无限次参数visited 数组start传 i1indexstart传 ifor 起点每次从 0 开始从 start 开始从 0 开始新映射串从 start 开始收集时机叶子节点每次进入叶子节点sum target关键点顺序关心 → 每次从 0 开始visited顺序不关心 → start 参数往后选。元素可复用 → 传 i不可复用 → 传 i1复杂度分析时间复杂度最坏 O(N^(target/min))N 是候选数字个数target/min 是最大递归深度min 是最小的候选数。实际有剪枝运行速度更快空间复杂度O(target/min)递归深度最深的情况