当前位置：首页 > news >正文

LeetCode 39：组合总和——Java DFS 回溯与剪枝详解

news 2026/8/12 21:24:10

一、题目描述

给定一个无重复元素的正整数数组candidates和一个目标整数target，找出所有数字之和等于target的不同组合。

数组中的同一个数字可以被重复选择。如果至少有一个数字的选择次数不同，就认为是不同组合。题目允许以任意顺序返回答案。

例如：

输入：candidates = [2, 3, 6, 7], target = 7 输出：[[2, 2, 3], [7]]

数字2可以重复使用，因此可以得到组合[2,2,3]；数字7本身也等于目标值，所以[7]也是一个有效组合。

这道题的难点主要有两个：

同一个数字可以无限次使用；
[2,2,3]和[3,2,2]只能算作一种组合。

解决这两个问题的关键，就是DFS、回溯和start起始下标。

二、把组合过程看成一棵决策树

假设：

candidates = [3, 4, 5], target = 9

从空组合开始，第一轮可以选择3、4或5。选择一个数字后，再继续选择下一个数字，直到当前总和等于或者超过target。

例如，先选择3，当前路径为[3]，总和为3。因为数字可以重复使用，下一层仍然可以选择3，得到[3,3]；继续选择3后得到[3,3,3]，总和正好为9，因此找到一个有效组合。

如果先选择4，再选择5，可以得到[4,5]。但如果第一轮选择5，第二轮再选择4，就会得到[5,4]。两者包含的数字和数量完全相同，本质上是同一种组合，不能重复加入答案。

因此，我们不能让每一层都从数组下标0开始遍历，而要通过一个start参数控制下一层的选择范围。

三、`start`如何避免重复组合

start表示当前这一层可以从candidates的哪个位置开始选择。

for (int i = start; i < candidates.length; i++) { // 选择 candidates[i] }

假设当前第一次选择的是下标1对应的数字4，那么后续只能继续选择下标大于或等于1的数字，即4和5，不能再回头选择下标0的数字3。

这样一来，可以生成[4,5]，但不会再生成顺序相反的[5,4]。所有组合都会按照候选数组中的下标顺序构造，从而自然避免重复。

这里要区分两个容易混淆的概念：

start限制的是当前层可以选择的起点，用来避免不同排列产生重复组合；
递归时传入i，而不是i + 1，用来允许当前数字被重复使用。

核心递归调用如下：

traverseTree(candidates, target, i);

如果传入i + 1，当前数字在下一层就不能再次被选择，这将变成“每个数字最多使用一次”的另一类组合问题。

可以把这条规律记成一句话：

start负责去重，传入i负责复用。

四、递归终止条件与剪枝

搜索过程中需要根据当前路径总和sum判断是否继续递归。

1. 找到有效组合

当sum == target时，说明当前路径是一组有效答案：

if (sum == target) { res.add(new ArrayList<>(route)); return; }

这里必须创建一个新的ArrayList，保存当前路径的快照。不能直接将route放入结果集，因为route在后续回溯过程中还会继续修改。

2. 当前总和超过目标值

当sum > target时，可以直接结束当前分支：

if (sum > target) { return; }

题目保证候选数字都是正整数。总和一旦超过target，继续添加数字只会使总和更大，当前分支不可能再得到有效答案，因此可以提前剪枝。

例如目标值为9，当前路径为[5,5]，总和已经是10，就没有继续搜索的必要。

五、回溯的完整过程

在每一层递归中，需要完成“选择、递归、撤销选择”三个动作：

route.add(candidates[i]); sum += candidates[i]; traverseTree(candidates, target, i); route.removeLast(); sum -= candidates[i];

先把当前数字加入路径并更新总和，然后进入下一层继续搜索。递归返回后，删除刚刚加入的数字，同时恢复sum，让程序回到选择该数字之前的状态，再尝试同一层的其他候选数字。

例如搜索[3,3,3]并记录答案后，需要依次回退到[3,3]、[3]。只有恢复原来的路径和总和，才能继续尝试[3,3,4]、[3,4]等其他分支。

如果只删除路径末尾元素，却没有恢复sum，路径和总和就会不一致，后面的判断也会全部出错。

六、完整 Java 代码

下面的实现与上述思路一致：

import java.util.ArrayList; import java.util.LinkedList; import java.util.List; class Solution { // 保存所有符合条件的组合 private final List<List<Integer>> res = new LinkedList<>(); // 保存当前搜索路径 private final LinkedList<Integer> route = new LinkedList<>(); // 当前路径中所有数字之和 private int sum = 0; public List<List<Integer>> combinationSum(int[] candidates, int target) { traverseTree(candidates, target, 0); return res; } private void traverseTree(int[] candidates, int target, int start) { // 当前路径正好满足要求 if (sum == target) { res.add(new ArrayList<>(route)); return; } // 数组元素均为正数，超过目标值后无法再恢复 if (sum > target) { return; } // 只从 start 开始选择，避免产生重复排列 for (int i = start; i < candidates.length; i++) { // 做出选择 route.add(candidates[i]); sum += candidates[i]; // 仍从 i 开始，允许 candidates[i] 被重复选择 traverseTree(candidates, target, i); // 撤销选择，恢复进入递归前的状态 route.removeLast(); sum -= candidates[i]; } } }