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（下次从 start+1 开始）	start（下次从start（含自己）开始）

核心区别：子集递归时传i + 1（不能再选自己），组合总和递归时传i（可以继续选自己）

思路概览

classSolution{privatefinalList<List<Integer>>result=newArrayList<>();privatefinalList<Integer>path=newArrayList<>();privateintsum=0;publicList<List<Integer>>combinationSum(int[]candidates,inttarget){if(candidates==null||candidates.length==0){returnnewArrayList<>();}backtrack(candidates,target,0);returnresult;}privatevoidbacktrack(int[]candidates,inttarget,intstart){if(sum==target){result.add(newArrayList<>(path));return;}if(sum>target){return;}for(inti=start;i<candidates.length;i++){path.add(candidates[i]);sum+=candidates[i];backtrack(candidates,target,i);sum-=candidates[i];path.removeLast();}}}

思路简要说明

两个终止条件：sum == target时收集结果；sum > target时剪枝返回
start 参数：控制"只往后选"，避免 [2,3] 和 [3,2] 重复
递归传 i 不是 i+1：允许重复选择当前元素

三、思路详解

第一步：为什么不能用前缀和

看到"数组求和 = target"，很多人第一反应是排序 + 前缀和。但仔细看题目：

问题一：结果不是连续子数组

前缀和解决的是"从原数组中找一段连续的子数组"，但本题的组合可以从任意位置挑，比如 candidates = [2, 3, 6, 7] 中挑 [2, 2, 3]，2 用了两次，位置也不连续

问题二：可以重复选择

前缀和的每个元素只被计算一次，本题允许一个元素被选无数次，前缀和天然做不到

所以只能回溯——枚举所有可能的选择路径

第二步：为什么用 start 参数

如果不控制顺序，[2, 3] 和 [3, 2] 会被算成两个组合，题目视为重复。解决办法是规定只往后选——每次选完一个元素后，下次选择只能从当前位置开始往后

以 candidates = [2, 3, 6, 7]，target = 7 为例：

选 2（i=0）后，下次只能从 i=0 开始（含 2 自己），即 {2, 3, 6, 7} 选 2（i=0）后，下次还是从 i=0 开始 选 2 → sum=6，继续 ... 选 3（i=1）后，下次从 i=1 开始（含 3），即 {3, 6, 7} 不能回头选 2，否则会出现 [2, 3, 2] 和 [2, 2, 3] 重复

这样保证每个组合的元素只按数组下标非递减顺序排列，天然去重

第三步：递归传 i 而不是 i+1

这是和子集问题最大的区别：

// 子集：每个元素最多选 1 次backtrack(res,i+1,nums,subset);// 组合总和：可以重复选择backtrack(candidates,target,i);

传i意味着"下次可以再选自己"，实现了元素的重复选择。以 candidates = [2, 3, 6, 7]，选到 2 之后：

第一次选 2 → path=[2] 递归传 i=0，下次仍可以选 2 第二次选 2 → path=[2, 2] 递归传 i=0，下次仍可以选 2 第三次选 2 → path=[2, 2, 2]，sum=6 < 7 ...

第四步：两个终止条件

if(sum==target){result.add(newArrayList<>(path));return;}if(sum>target){return;}

sum == target：找到一个合法组合，收集后返回
sum > target：当前路径已经超出目标，继续往下加只会更大，直接剪枝返回

因为 candidates 都是正数，sum 只会越加越大，所以超过就没必要继续

第五步：回溯操作

for 循环内的四行代码是回溯的核心：

path.add(candidates[i]);// 选：加入路径sum+=candidates[i];// 选：更新总和backtrack(candidates,target,i);// 往下递归sum-=candidates[i];// 撤销：恢复总和path.removeLast();// 撤销：移除路径最后一个

选就是 add + sum+=，撤销就是 sum-= + removeLast。每次选完往深处走，回来后完整撤销，for 循环 i++ 换下一个元素

第六步：完整执行过程

以 candidates = [2, 3, 6, 7]，target = 7 为例：

backtrack(start=0, path=[], sum=0) ├── 选 2 → path=[2], sum=2 │ └── backtrack(start=0) │ ├── 选 2 → path=[2,2], sum=4 │ │ └── backtrack(start=0) │ │ ├── 选 2 → path=[2,2,2], sum=6 │ │ │ └── backtrack(start=0) │ │ │ ├── 选 2 → sum=8 > 7，剪枝 │ │ │ ├── 选 3 → sum=9 > 7，剪枝 │ │ │ ├── 选 6 → sum=12 > 7，剪枝 │ │ │ └── 选 7 → sum=13 > 7，剪枝 │ │ ├── 选 3 → path=[2,2,3], sum=7 ✓ 收集 [2,2,3] │ │ ├── 选 6 → sum=10 > 7，剪枝 │ │ └── 选 7 → sum=11 > 7，剪枝 │ ├── 选 3 → path=[2,3], sum=5 │ │ └── backtrack(start=1) │ │ ├── 选 3 → sum=8 > 7，剪枝 │ │ ├── 选 6 → sum=11 > 7，剪枝 │ │ └── 选 7 → sum=12 > 7，剪枝 │ ├── 选 6 → sum=8 > 7，剪枝 │ └── 选 7 → sum=9 > 7，剪枝 ├── 选 3 → path=[3], sum=3 │ └── backtrack(start=1) │ ├── 选 3 → path=[3,3], sum=6 │ │ └── 后面都超，剪枝 │ ├── 选 6 → sum=9，剪枝 │ └── 选 7 → sum=10，剪枝 ├── 选 6 → path=[6], sum=6 │ └── backtrack(start=2) │ ├── 选 6 → sum=12，剪枝 │ └── 选 7 → sum=13，剪枝 └── 选 7 → path=[7], sum=7 ✓ 收集 [7]

最终结果：[[2, 2, 3], [7]]

第七步：和之前几道题的对比

全排列	子集（方法二）	电话号码	组合总和
顺序	关心	不关心	关心	不关心
元素能选几次	1 次	1 次（选/不选）	1 次（多选一）	无限次
参数	visited 数组	start（传 i+1）	index	start（传 i）
for 起点	每次从 0 开始	从 start 开始	从 0 开始（新映射串）	从 start 开始
收集时机	叶子节点	每次进入	叶子节点	sum == target