LeetCode 题解工作台
组合总和 II
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意： 解集不能包含重复的组合。 示例 1: 输入: candidates = […
2
题型
9
代码语言
3
相关题
当前训练重点
中等 · 回溯·pruning
答案摘要
我们可以先对数组进行排序，方便剪枝以及跳过重复的数字。 接下来，我们设计一个函数 $dfs(i, s)$，表示从下标 开始搜索，且剩余目标值为 ，其中 和 都是非负整数，当前搜索路径为 ，答案为 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates =[10,1,2,7,6,1,5], target =8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ]
提示:
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
解题思路
方法一：排序 + 剪枝 + 回溯
我们可以先对数组进行排序，方便剪枝以及跳过重复的数字。
接下来，我们设计一个函数 ，表示从下标 开始搜索，且剩余目标值为 ，其中 和 都是非负整数，当前搜索路径为 ，答案为 。
在函数 中，我们先判断 是否为 ，如果是，则将当前搜索路径 加入答案 中，然后返回。如果 ，或者 ，说明当前路径不合法，直接返回。否则，我们从下标 开始搜索，搜索的下标范围是 ，其中 为数组 的长度。在搜索的过程中，如果 并且 ，说明当前数字与上一个数字相同，我们可以跳过当前数字，因为上一个数字已经搜索过了。否则，我们将当前数字加入搜索路径 中，然后递归调用函数 ，然后将当前数字从搜索路径 中移除。
在主函数中，我们只要调用函数 ，即可得到答案。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。由于剪枝，实际的时间复杂度要远小于 。
相似题目：
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(i: int, s: int):
if s == 0:
ans.append(t[:])
return
if i >= len(candidates) or s < candidates[i]:
return
for j in range(i, len(candidates)):
if j > i and candidates[j] == candidates[j - 1]:
continue
t.append(candidates[j])
dfs(j + 1, s - candidates[j])
t.pop()
candidates.sort()
ans = []
t = []
dfs(0, target)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(2^N) due to exploring subsets of candidates, and space complexity is O(N) for the recursion stack and temporary combination path storage. |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Check if candidates are sorted to simplify duplicate handling.
- question_mark
Ask about pruning early when sum exceeds target.
- question_mark
Probe understanding of skipping duplicates in backtracking to avoid repeated combinations.
常见陷阱
外企场景- error
Not sorting candidates first, which complicates duplicate skipping.
- error
Using a candidate multiple times per combination when only single use is allowed.
- error
Failing to prune recursion early, leading to excessive computation and timeouts.
进阶变体
外企场景- arrow_right_alt
Combination Sum (allowing unlimited usage of candidates).
- arrow_right_alt
Target Sum with negative numbers included, requiring careful pruning.
- arrow_right_alt
Finding combinations of a fixed length that sum to the target.