组合总和(Combination Sum)
好的，今天咱们来聊一个经典的面试题，也是组合数学里的常客——组合总和 (Combination Sum)。
这道题挺有意思，它能很好地体现一个程序员从暴力到优化的思维过程。咱们的目标不是把它AC了就完事，而是要把里面的套路吃透，以后遇到类似的什么排列、组合、子集问题，脑子里得立马有思路。
题目描述
给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为 target 的所有不同组合。
candidates 中的每个数字在每个组合中可以使用任意次。
解集不能包含重复的组合。
举个例子： candidates = [2, 3, 6, 7], target = 7 输出：[[2, 2, 3], [7]]
解法一：暴力搜索，也叫回溯，或者叫深度优先遍历（DFS）
拿到这种题，第一时间想不到什么花里胡哨的动态规划，脑子里最朴素的想法是啥？
一个字，试。
我先拿个2，目标还剩7 - 2 = 5。接下来我还能不能拿2？题上说可以，那我就再拿个2，目标还剩5 - 2 = 3。还能拿2吗？再拿就小于0了，不行。那我试试3，目标还剩3 - 3 = 0。嘿，凑够了！找到一个解 [2, 2, 3]。
记下来之后怎么办？得回去啊，回到刚才拿了第二个2还剩3那一步。我不拿3了，试试拿6，3-6小于0，不行。试试7，也不行。
这个过程，一步步往前走，走不通了就退回来换条路再走，这不就是典型的递归+回溯嘛。
咱们来定义一个递归函数 dfs(candidates, target, startIndex)。为啥要有个 startIndex？这是个关键点。为了防止出现[2,3]和[3,2]这种重复组合，我们得定个规矩：在每一层递归里，你只能选当前数字或者它后面的数字，不能往回选。
笔给你，你怎么画这个递归树？
dfs(target=7, startIndex=0)
/ | | \
选2 / |选3 |选6 \选7
v v v v
dfs(target=5, start=0) dfs(t=4, s=1) dfs(t=1, s=2) dfs(t=0, s=3) -> 找到[7]
/ | \
选2 / |选3 \选6
v v v
dfs(t=3, s=0) dfs(t=2,s=1) dfs(t=-1,s=2) -> 剪掉
/ |
选2 / |选3
v v
dfs(t=1,s=0) dfs(t=0,s=1) -> 找到[2,2,3]
好了，思路清晰了，上代码。
import java.util.ArrayList;
import java.util.List;
public class CombinationSum {
// 解法一：纯暴力回溯
public List<List<Integer>> combinationSum1(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (candidates == null || candidates.length == 0) {
return result;
}
// 用一个 path 记录当前路径上的数字
List<Integer> path = new ArrayList<>();
dfs(candidates, target, 0, path, result);
return result;
}
/**
* @param candidates 候选数组
* @param target 剩余目标值
* @param startIndex 本轮搜索的起始位置
* @param path 从根节点到当前节点的路径
* @param result 最终结果集
*/
private void dfs(int[] candidates, int target, int startIndex, List<Integer> path, List<List<Integer>> result) {
// 递归终止条件1：target 小于 0，说明这条路走不通
if (target < 0) {
return;
}
// 递归终止条件2：target 等于 0，说明找到了一组解
if (target == 0) {
// 注意！这里必须 new một个新的 List，因为 path 是引用传递，后面会回溯修改
result.add(new ArrayList<>(path));
return;
}
// 遍历选择
for (int i = startIndex; i < candidates.length; i++) {
// 做出选择
path.add(candidates[i]);
// 递归进入下一层
// 注意！因为数字可以重复使用，所以下一层的 startIndex 仍然是 i
dfs(candidates, target - candidates[i], i, path, result);
// 撤销选择（回溯）
path.remove(path.size() - 1);
}
}
}
这代码很标准，也很暴力。它会把所有可能性都给你探一遍，只要不撞南墙（target < 0）就不回头。有没有优化的空间？当然有。
解法二：回溯 + 剪枝
上面的暴力解法有什么问题？
假如 candidates = [7, 6, 3, 2]，target = 7。 当我第一层选了7，下一层递归 dfs(target=0, ...)，找到了解。 然后回溯，第一层不选7了，改选6，下一层递归dfs(target=1, ...)。在这一层里，你是不是还得把6, 3, 2都试一遍？这不纯纯浪费时间嘛，1比它们都小，根本不可能凑出来。
所以，一个非常自然而然的想法就出来了：剪枝。
如果我先把数组排个序，比如 [2, 3, 6, 7]。 在某一层递归中，当我发现当前的 target 已经小于 candidates[i] 了，那还有必要去试 candidates[i+1]、candidates[i+2] 吗？没必要了，因为后面的数更大，更不可能凑齐。
所以，优化点就是：
先排序。
在循环里加一个判断，如果
target - candidates[i] < 0，直接break，后面的不用试了。
代码改动极小，但性能提升可能非常明显。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CombinationSum {
// 解法二：排序 + 剪枝的回溯
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (candidates == null || candidates.length == 0) {
return result;
}
// 关键第一步：排序，为剪枝做准备
Arrays.sort(candidates);
List<Integer> path = new ArrayList<>();
dfsWithPruning(candidates, target, 0, path, result);
return result;
}
private void dfsWithPruning(int[] candidates, int target, int startIndex, List<Integer> path, List<List<Integer>> result) {
if (target == 0) {
result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
// 剪枝！如果当前数字已经比剩余的 target 大，那后面的更大，肯定也不行
if (target - candidates[i] < 0) {
break; // 因为数组已排序，所以可以直接结束循环
}
path.add(candidates[i]);
dfsWithPruning(candidates, target - candidates[i], i, path, result);
path.remove(path.size() - 1);
}
}
}
这个版本是不是感觉思路更清晰了？先排序，再暴力，遇到走不通的死胡同（剪枝）就提前掉头。这是解决这类搜索问题的一个通用优化技巧。
解法三：动态规划
回溯是从target往下减，一路减到0。那我们能不能换个思路，从0往上加，一直加到target呢？
这就是动态规划的思路了。自底向上地构建答案。
咱们定义一个 dp 数组（或者 Map，这里用 List 数组更直观），dp[i] 表示目标和为 i 的所有组合。我们的最终目标就是 dp[target]。
dp[0]是什么？和为0的组合，只有一个，就是空集[]。所以dp[0]应该包含一个空的List。这是我们的 base case。dp[1]怎么求？遍历candidates数组，假设里面有1，那dp[1]就是在dp[1-1]也就是dp[0]的基础上，每个组合都加上1。dp[i]怎么求？它可以由dp[i - candidate]转换而来。遍历每一个candidate，对于dp[i - candidate]里的每一个组合，都把它拿出来，添上这个candidate，就成了dp[i]的一个新组合。
举个例子：candidates = [2, 3], target = 7 dp 数组大小为 8
dp[0] = [[]] dp[1] = [] dp[2] = ? - 看看 candidate = 2：看 dp[2-2] = dp[0] = [[]]。把 [] 加上 2，得到 [2]。 - dp[2] = [[2]] dp[3] = ? - 看看 candidate = 2：看 dp[3-2] = dp[1] = []。没组合。 - 看看 candidate = 3：看 dp[3-3] = dp[0] = [[]]。把 [] 加上 3，得到 [3]。 - dp[3] = [[3]] dp[4] = ? - 看看 candidate = 2：看 dp[4-2] = dp[2] = [[2]]。把 [2] 加上 2，得到 [2, 2]。 - 看看 candidate = 3：看 dp[4-3] = dp[1] = []。没组合。 - dp[4] = [[2, 2]] ... 一直算到 dp[7]。
这个过程是不是有点像爬楼梯或者背包问题？没错，它就是完全背包问题的一种变形，求的是方案数，只不过我们这里要求的是所有具体方案。
上代码！
import java.util.ArrayList;
import java.util.List;
public class CombinationSum {
// 解法三：动态规划
public List<List<Integer>> combinationSum3(int[] candidates, int target) {
// dp[i] 表示目标和为 i 的所有组合
List<List<List<Integer>>> dp = new ArrayList<>(target + 1);
// 初始化 dp 数组
for (int i = 0; i <= target; i++) {
dp.add(new ArrayList<>());
}
// base case: 和为 0 的组合就是空集
dp.get(0).add(new ArrayList<>());
// 遍历物品（candidates）
for (int coin : candidates) {
// 遍历背包容量（从 coin 开始到 target）
for (int i = coin; i <= target; i++) {
// dp[i] 的解可以由 dp[i - coin] 转换而来
List<List<Integer>> prevCombinations = dp.get(i - coin);
for (List<Integer> prevCombo : prevCombinations) {
// 创建一个新的组合，在旧组合的基础上加上当前 coin
List<Integer> newCombo = new ArrayList<>(prevCombo);
newCombo.add(coin);
dp.get(i).add(newCombo);
}
}
}
return dp.get(target);
}
}
这个DP解法就把问题从搜索转换成了状态转移，思路完全不同。但要注意，DP的空间复杂度可能会很高，因为它要存储从0到target所有中间状态的解。如果target很大，或者中间解特别多，内存可能会爆。
总结一下
你看，同一道题，三种完全不同的思考路径：
暴力回溯：最直观，最容易想到的方法。先把架子搭起来，能跑就行。这是解决问题的基础。
回溯 + 剪枝：在暴力的基础上思考“有没有冗余的计算？”。通过排序，剔除掉那些明显不可能产生解的搜索分支。这是优化的第一步，也是面试中展现你思考深度的地方。
动态规划：完全换一个角度看问题。从“由上到下，分而治之”变成“由下到上，逐步构建”。这体现了你对算法模型（比如背包问题）的熟悉程度和抽象建模能力。