LeetCode 40: Combination Sum II (Backtracking + Duplicate Pruning)
LeetCode 40BacktrackingDuplicate PruningToday we solve LeetCode 40 - Combination Sum II.
Source: https://leetcode.com/problems/combination-sum-ii/
English
Problem Summary
Given a collection of candidate numbers (which may contain duplicates) and a target number, return all unique combinations where chosen numbers sum to target. Each number can be used at most once.
Key Insight
Sort first. During DFS, process candidates from left to right and move to i + 1 after picking candidates[i] (single-use constraint). To avoid duplicate combinations, skip equal values when they appear at the same recursion level: if (i > start && candidates[i] == candidates[i - 1]) continue.
Brute Force and Why Insufficient
Enumerating all subsets is O(2^n), and handling duplicates afterward via a set is expensive and messy. Sorted backtracking with in-search pruning removes duplicate branches early.
Optimal Algorithm (Step-by-Step)
1) Sort candidates ascending.
2) DFS parameters: start, remain, current path.
3) If remain == 0, record a copy of path.
4) Loop i from start to end:
- If i > start and current equals previous, skip (same-layer duplicate).
- If candidates[i] > remain, break (sorted prune).
- Choose value, recurse with dfs(i + 1, remain - candidates[i]), then backtrack.
5) Return collected answers.
Complexity Analysis
Time: worst-case exponential, commonly written as O(2^n) with pruning benefits in practice.
Space: O(n) recursion depth excluding output.
Common Pitfalls
- Forgetting to sort before duplicate pruning.
- Using dfs(i, ...) and unintentionally reusing the same element.
- Misplacing duplicate check so valid branches get skipped.
- Missing early break when current value exceeds remaining target.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> ans = new ArrayList<>();
backtrack(candidates, target, 0, new ArrayList<>(), ans);
return ans;
}
private void backtrack(int[] a, int remain, int start, List<Integer> path, List<List<Integer>> ans) {
if (remain == 0) {
ans.add(new ArrayList<>(path));
return;
}
for (int i = start; i < a.length; i++) {
if (i > start && a[i] == a[i - 1]) continue;
if (a[i] > remain) break;
path.add(a[i]);
backtrack(a, remain - a[i], i + 1, path, ans);
path.remove(path.size() - 1);
}
}
}import "sort"
func combinationSum2(candidates []int, target int) [][]int {
sort.Ints(candidates)
ans := [][]int{}
path := []int{}
var dfs func(start, remain int)
dfs = func(start, remain int) {
if remain == 0 {
tmp := append([]int{}, path...)
ans = append(ans, tmp)
return
}
for i := start; i < len(candidates); i++ {
if i > start && candidates[i] == candidates[i-1] {
continue
}
if candidates[i] > remain {
break
}
path = append(path, candidates[i])
dfs(i+1, remain-candidates[i])
path = path[:len(path)-1]
}
}
dfs(0, target)
return ans
}class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> ans;
vector<int> path;
dfs(candidates, target, 0, path, ans);
return ans;
}
void dfs(vector<int>& a, int remain, int start, vector<int>& path, vector<vector<int>>& ans) {
if (remain == 0) {
ans.push_back(path);
return;
}
for (int i = start; i < (int)a.size(); ++i) {
if (i > start && a[i] == a[i - 1]) continue;
if (a[i] > remain) break;
path.push_back(a[i]);
dfs(a, remain - a[i], i + 1, path, ans);
path.pop_back();
}
}
};class Solution:
def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
candidates.sort()
ans: list[list[int]] = []
path: list[int] = []
def dfs(start: int, remain: int) -> None:
if remain == 0:
ans.append(path.copy())
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i - 1]:
continue
if candidates[i] > remain:
break
path.append(candidates[i])
dfs(i + 1, remain - candidates[i])
path.pop()
dfs(0, target)
return ansvar combinationSum2 = function(candidates, target) {
candidates.sort((a, b) => a - b);
const ans = [];
const path = [];
const dfs = (start, remain) => {
if (remain === 0) {
ans.push([...path]);
return;
}
for (let i = start; i < candidates.length; i++) {
if (i > start && candidates[i] === candidates[i - 1]) continue;
if (candidates[i] > remain) break;
path.push(candidates[i]);
dfs(i + 1, remain - candidates[i]);
path.pop();
}
};
dfs(0, target);
return ans;
};中文
题目概述
给定一个可能包含重复元素的数组 candidates 和目标值 target，找出所有和为 target 的不重复组合。每个元素最多只能使用一次。
核心思路
先排序，再回溯。由于每个元素只能用一次，递归下一层从 i + 1 开始。为避免重复组合，在同一层循环里跳过相同值：if (i > start && a[i] == a[i-1]) continue。
朴素解法与不足
如果直接枚举所有子集再去重，会产生大量重复中间结果，时间和空间都不友好。排序 + 层内去重可以在搜索过程中直接剪枝。
最优算法（步骤）
1）先将 candidates 升序排序。
2）定义回溯参数：起点 start、剩余目标 remain、当前路径。
3）当 remain == 0 时，记录当前路径副本。
4）从 start 开始遍历索引 i：
- 若 i > start 且当前值等于前一个值，跳过（同层去重）；
- 若 a[i] > remain，可直接 break（有序剪枝）；
- 选择 a[i]，递归 dfs(i+1, remain-a[i])，返回后撤销选择。
5）最终返回所有答案。
复杂度分析
时间复杂度：最坏接近 O(2^n)，但排序与剪枝可显著减少实际分支。
空间复杂度：递归栈深度 O(n)（不计输出结果）。
常见陷阱
- 忘记排序导致“同层去重”失效。
- 递归仍传 i 而不是 i+1，错误复用元素。
- 去重条件写错位置，误删合法组合。
- 漏掉 a[i] > remain 的提前终止。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> ans = new ArrayList<>();
backtrack(candidates, target, 0, new ArrayList<>(), ans);
return ans;
}
private void backtrack(int[] a, int remain, int start, List<Integer> path, List<List<Integer>> ans) {
if (remain == 0) {
ans.add(new ArrayList<>(path));
return;
}
for (int i = start; i < a.length; i++) {
if (i > start && a[i] == a[i - 1]) continue;
if (a[i] > remain) break;
path.add(a[i]);
backtrack(a, remain - a[i], i + 1, path, ans);
path.remove(path.size() - 1);
}
}
}import "sort"
func combinationSum2(candidates []int, target int) [][]int {
sort.Ints(candidates)
ans := [][]int{}
path := []int{}
var dfs func(start, remain int)
dfs = func(start, remain int) {
if remain == 0 {
tmp := append([]int{}, path...)
ans = append(ans, tmp)
return
}
for i := start; i < len(candidates); i++ {
if i > start && candidates[i] == candidates[i-1] {
continue
}
if candidates[i] > remain {
break
}
path = append(path, candidates[i])
dfs(i+1, remain-candidates[i])
path = path[:len(path)-1]
}
}
dfs(0, target)
return ans
}class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> ans;
vector<int> path;
dfs(candidates, target, 0, path, ans);
return ans;
}
void dfs(vector<int>& a, int remain, int start, vector<int>& path, vector<vector<int>>& ans) {
if (remain == 0) {
ans.push_back(path);
return;
}
for (int i = start; i < (int)a.size(); ++i) {
if (i > start && a[i] == a[i - 1]) continue;
if (a[i] > remain) break;
path.push_back(a[i]);
dfs(a, remain - a[i], i + 1, path, ans);
path.pop_back();
}
}
};class Solution:
def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
candidates.sort()
ans: list[list[int]] = []
path: list[int] = []
def dfs(start: int, remain: int) -> None:
if remain == 0:
ans.append(path.copy())
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i - 1]:
continue
if candidates[i] > remain:
break
path.append(candidates[i])
dfs(i + 1, remain - candidates[i])
path.pop()
dfs(0, target)
return ansvar combinationSum2 = function(candidates, target) {
candidates.sort((a, b) => a - b);
const ans = [];
const path = [];
const dfs = (start, remain) => {
if (remain === 0) {
ans.push([...path]);
return;
}
for (let i = start; i < candidates.length; i++) {
if (i > start && candidates[i] === candidates[i - 1]) continue;
if (candidates[i] > remain) break;
path.push(candidates[i]);
dfs(i + 1, remain - candidates[i]);
path.pop();
}
};
dfs(0, target);
return ans;
};
Comments