企业官网建设流程全解析

• 教程
• 文档

导读

本文基于「宫水三叶的刷题日记」系列仓库中的 40. 组合总和 II 题解，深入讲解 LeetCode 第 40 题「组合总和 II」的 DFS + 回溯解法。该题与「39. 组合总和」几乎同源，核心差异在于每个数字在每个组合中只能使用一次，且candidates中可能包含重复元素，因此去重成为本题的关键难点。读完本文，你将掌握：如何快速判断一道题是否适合用 DFS + 回溯爆搜、如何在「每个数只能用一次」的约束下实现选/不选决策、如何通过排序 + Set 保证解集不重复，以及该解法的时间与空间复杂度边界。

题目描述与约束分析

题目：给定一个数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。

与 39 题的关键区别：

• 本题中candidates中的每个数字在每个组合中只能使用一次；
• 而 39. 组合总和 中数字可以无限制重复被选取。

题目约束说明：

• 所有数字（包括目标数target）都是正整数；
• 解集不能包含重复的组合。

示例 1：

输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]

注意观察：candidates中有两个1，解集中出现了[1, 1, 6]（两个不同的1各用一次），但不能出现两个[1, 7]或两个[1, 2, 5]（即不能因为"用第一个 1"和"用第二个 1"而产出重复组合）。

示例 2：

输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]

这里candidates中有三个2，解集中[1,2,2]恰好使用了两个2，且只出现一次。

本题的数据范围与 39 题一致：1 <= candidates.length <= 30，1 <= candidates[i] <= 200，1 <= target <= 500。

如何判断一道题该用 DFS + 回溯

在动笔写代码之前，先回答一个方法论问题：为什么这道题适合 DFS + 回溯爆搜？该判断方法最早由作者在 37. 解数独（困难） 的题解中提出，之后在 39、40、90 等多道题中反复复用，可以从两个方面来考虑：

1. 求的是所有的方案，而不是方案数。由于求的是所有方案，不可能有什么特别的优化，我们只能进行枚举。此时可能的解法有动态规划、记忆化搜索、DFS + 回溯算法。本题要求"找出所有可以使数字和为 target 的组合"，显然是求全部方案，因此落入回溯的射程。

2. 通常数据范围不会太大，只有几十。如果是动态规划或记忆化搜索的题，由于它们的特点在于低重复/不重复枚举，数据范围一般可以出到 $10^4 \sim 10^7$；而 DFS + 回溯是"指数级"爆搜，通常会限制在 30 以内。本题candidates.length <= 30，恰好符合。

结论：这道题数据范围在 30 以内，而且求的是所有方案，因此使用 DFS + 回溯来求解。类似的判断逻辑在仓库的 回溯算法索引 与 DFS 索引 中列出的一众题目（如 17、37、39、90、131 等）里被反复验证。

与 39 题的思路对比：从"无限次"到"一次"

39. 组合总和 的 DFS 代码核心是枚举cs[u]的使用次数：

// 枚举 cs[u] 的使用次数 for (int i = 0; cs[u] * i <= t; i++) { dfs(cs, t - cs[u] * i, u + 1, ans, cur); cur.add(cs[u]); } // 进行回溯。注意回溯总是将数组的最后一位弹出 for (int i = 0; cs[u] * i <= t; i++) { cur.remove(cur.size() - 1); }

因为 39 题中每个数可以重复使用，所以决策的对象是"某个数用几次"；而 40 题中每个数最多用一次，决策对象退化为"某个数用还是不用"，代码因此可以大幅简化。这就是作者所说的"接着 39 的思路来修改"。

DFS + 回溯解法（排序 + Set 去重）

核心思路

在 40. 组合总和 II 题解 中，作者给出了两个关键改造点：

1. 由于每个数字只能使用一次，可以直接在 DFS 中决策某个数是用还是不用。即递归的两个分支：选cs[u]（剩余目标减cs[u]，下标u + 1）与不选cs[u]（剩余目标不变，下标u + 1）。

2. 由于不允许重复答案，使用Set保存所有合法方案，最终再转为List返回。但直接去重是不够的，必须先对cs进行排序，确保得到的合法方案中数值都是从小到大排列的，这样Set才能起到去重作用。对于[1,2,1]和[1,1,2]，若不排序，Set不会认为是相同的数组；排序后两个组合都会规整为[1,1,2]，从而被正确判重。

完整代码（Java）

class Solution { public List<List<Integer>> combinationSum2(int[] cs, int t) { Arrays.sort(cs); Set<List<Integer>> ans = new HashSet<>(); List<Integer> cur = new ArrayList<>(); dfs(cs, t, 0, ans, cur); return new ArrayList<>(ans); } /** * cs: 原数组，从该数组进行选数 * t: 还剩多少值需要凑成。起始值为 target ，代表还没选择任何数；当 t = 0，代表选择的数凑成了 target * u: 当前决策到 cs[] 中的第几位 * ans: 最终结果集 * cur: 当前结果集 */ void dfs(int[] cs, int t, int u, Set<List<Integer>> ans, List<Integer> cur) { if (t == 0) { ans.add(new ArrayList<>(cur)); return; } if (u == cs.length || t < 0) return; // 使用 cs[u] cur.add(cs[u]); dfs(cs, t - cs[u], u + 1, ans, cur); // 进行回溯 cur.remove(cur.size() - 1); // 不使用 cs[u] dfs(cs, t, u + 1, ans, cur); } }

递归状态与终止条件解读

• t（剩余目标值）：起始值为target，代表还没选择任何数；当t == 0时说明当前cur中的数字恰好凑成target，是一个合法方案；当t < 0时说明当前路径已经超值，剪枝返回。
• u（决策下标）：表示当前决策到cs[]中的第几位。u == cs.length说明所有元素都已决策完毕，返回。
• 选/不选分支：先"选"后"不选"，中间用cur.remove(cur.size() - 1)完成回溯——将刚加入的cs[u]弹出，恢复现场后再走"不选"分支。回溯总是弹出数组的最后一位，这一点与 39 题的代码一致。

用示例 1 手工推演

以candidates = [10,1,2,7,6,1,5], target = 8为例：

1. 排序后得到cs = [1,1,2,5,6,7,10]；
2. DFS 从u = 0、t = 8开始，每个位置都有"选/不选"两个分支；
3. 当某条路径的t == 0时，将cur的副本放入ans。例如路径"选 1、选 7"得到[1,7]；路径"选 1、选 2、选 5"得到[1,2,5]；路径"选 2、选 6"得到[2,6]；路径"选两个 1、选 6"得到[1,1,6]；
4. 由于先排序，所有合法组合内部天然有序，[1,7]无论走"第一个 1"还是"第二个 1"的分支，最终生成的List都是[1,7]，被Set判为重复，只保留一份。

复杂度分析

• 时间复杂度：DFS 回溯算法通常是指数级复杂度（因此数据范围通常为 30 以内）。每个元素有选/不选两种决策，共 $2^n$ 个叶子节点，每个合法方案还需深拷贝一次（$O(n)$）。本题解中记为 $O(n \times 2^n)$，排序的 $O(n\log n)$ 被其覆盖。
• 空间复杂度：与时间复杂度同量级，最多存在 $2^n$ 个方案，每个方案占用 $O(n)$ 空间，复杂度为 $O(n \times 2^n)$。

为什么先排序 + Set 就够用

去重的本质是：把"不同决策路径产出相同数值集合"的情况合并。由于candidates中允许重复元素（示例 1 的两个1、示例 2 的三个2），同样的组合可以由不同的下标选择方案产生。先对数组排序，保证任何合法方案内部的元素都是非降序排列，于是"数值集合"与"有序列表"一一对应，Set<List<Integer>>便能把重复的组合过滤掉。

这一"排序 + Set 去重"的套路在仓库中的同族题目里被反复使用，例如 90. 子集 II（中等） 的"回溯解法（Set）"同样先Arrays.sort(nums)，再用Set<List<Integer>>去重。可见它是处理"含重复元素 + 求全部方案"这类回溯问题的通用模板。

去重的进阶思路：从 Set 到按值决策

值得一提的是，Set去重虽然简单，但HashSet的插入/查重只是均摊 O(1)。在 90. 子集 II 的题解中，作者进一步给出了不使用Set的去重方法，其思想对理解 40 题同样有启发：

使用Set的目的是为了去重，那什么时候会导致重复呢？其实就是相同的元素，不同的决策方案对应同样的结果。举个例：[1,1,1]的数据，只选择第一个和只选择第三个（不同的决策方案），结果是一样的。因此如果希望去重，不能单纯利用"某个下标是否被选择"来决策，而是要找到某个数值的连续一段，根据该数值的选择次数来决策——将决策方案从"某个下标是否被选择"修改为"相同的数值被选择的个数"。这样[1,1,1]不会因为"只选择第一个"和"只选择第三个"产生两个[1]，只会因为1被选择一次而产生一个[1]。

应用到 40 题中，可以同样把"对每个元素决策选/不选"改为"对每段相同数值决策选 k 个（k 从 0 到该段长度）"，配合target限制同样能得到不重复的全部方案。这是从"结果去重"走向"源头不产生重复"的进阶优化，也是回溯去重的核心心法。

题解在仓库中的定位

• 本文所依据的原始题解位于 LeetCode/31-40/40. 组合总和 II（中等）.md，同目录下还有与本题对比阅读的 39. 组合总和（中等）.md；
• 该方法论的出处 37. 解数独（困难）.md 中完整给出了"如何快速判断是否该用 DFS + 回溯"的框架；
• 仓库的 组合总和问题索引 将 39、40 两题归为同一 Tag，回溯算法索引 与 DFS 索引 则收录了更多采用相同"选/不选 + 回溯"模式的中等/困难题（如 17、90、131、301 等），可以作为同类题的刷题路线。

小结

• 题目本质：40 题是 39 题的"限量版"——每个数最多用一次，且候选数组含重复元素，导致"组合去重"成为核心难点；
• 解法选择依据：求全部方案 + 数据范围 ≤ 30，决定使用 DFS + 回溯爆搜；
• 两个关键改造：① 决策粒度从"用几次"降为"用或不用"，递归天然保证每个数至多用一次；② 先排序再配合Set去重，保证合法方案内部有序、重复组合被过滤；
• 复杂度边界：$O(n \times 2^n)$ 的时间与空间复杂度，解释了为何这类题目的数据范围必须限制在 30 以内；
• 延伸价值：排序 + Set 是处理"含重复元素的组合/子集类问题"的通用模板，进阶可按"相同数值的选择个数"决策实现无Set去重，参见仓库中 90 题的完整推演。

• 教程
• 文档