Missing undo step on backtrack
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.
A complete visual walkthrough of backtracking with duplicate skipping — the key twist that separates this from problem #39.
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5 Output: [ [1,2,2], [5] ]
Constraints:
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30Unlike problem #39, candidates can contain duplicates and each element may only be used once. A naive approach generates all subsets and checks their sums, but this produces duplicate combinations.
Expected output: [[1,1,6], [1,2,5], [1,7], [2,6]]
Without duplicate handling, we would get [1,2,5] twice — once using the first 1, once using the second 1.
After sorting, duplicate values are adjacent. The key rule is: at the same recursion level, if we have already tried a value, we skip any subsequent equal values.
if (i > start && candidates[i] == candidates[i - 1]) continue;
Together: if this is not the first sibling AND we equal the previous sibling, skip. This prevents duplicate combinations at the source without needing a HashSet post-filter.
Why i > start, not i > 0? Because start is where this recursion level begins its loop. The first iteration (i == start) must always run — it is the "first chance" to use this value. Only subsequent iterations with the same value should be skipped.
These two problems are nearly identical in structure. Let's highlight the exact differences:
| Aspect | #39 Combination Sum | #40 Combination Sum II |
|---|---|---|
| Reuse | Unlimited | Each element once |
| Input duplicates | All distinct | May have duplicates |
| Recursive call index | i (same index) | i + 1 (next index) |
| Dedup logic | Not needed | Skip if i>start && [i]==[i-1] |
Just two lines of difference! The recursive call uses i + 1 instead of i, and we add the duplicate-skipping continue statement. Everything else — the sort, the break on overshoot, the backtrack — is identical.
Let's trace with sorted candidates = [1, 1, 2, 5, 6, 7, 10], target = 8. We focus on how the duplicate-skip prevents redundant branches.
Crucial distinction: at level 1, i=1 is skipped because i > start (1 > 0) and candidates[1] == candidates[0]. But inside the [1] branch, i=1 is NOT skipped because now start=1, so i == start. This is how we allow [1, 1, 6] while preventing a duplicate [1, ...] branch at the top level.
After sorting, the skip rule (j > i && candidates[j] == candidates[j-1]) prevents picking duplicate starting points at the same recursion depth. Only one valid combination — [1,1] — is returned.
For example, candidates = [1,2,3], target = 2. The DFS picks 2 alone, reaches s == 0, and records [2]. Other paths with 1 also succeed: [1,1] is not possible here since each element is used once.
For example, candidates = [5,6,7], target = 4. The pruning condition s < candidates[i] (after sorting) causes every DFS call to return immediately, yielding an empty result.
LeetCode constraints guarantee target >= 1, so this edge case will not appear in practice. If it did, the base case if s == 0 fires before any candidate is picked, returning [[]].
For example, [1,1,1,1,1,1,2], target = 3. The skip logic must fire at every duplicate within the same loop iteration, not across different recursion depths — otherwise valid combos like [1,2] would be wrongly skipped.
class Solution { public List<List<Integer>> combinationSum2(int[] candidates, int target) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(candidates); // Sort to group duplicates backtrack(candidates, target, 0, new ArrayList<>(), result); return result; } private void backtrack(int[] candidates, int remain, int start, List<Integer> path, List<List<Integer>> result) { if (remain == 0) { // Target reached result.add(new ArrayList<>(path)); return; } for (int i = start; i < candidates.length; i++) { if (candidates[i] > remain) // Prune: too large break; if (i > start && candidates[i] == candidates[i - 1]) continue; // ← Skip duplicate at same level path.add(candidates[i]); // Choose backtrack(candidates, remain - candidates[i], i + 1, // ← i+1: no reuse path, result); path.remove(path.size() - 1); // Un-choose (backtrack) } } }
func combinationSum2(candidates []int, target int) [][]int { sort.Ints(candidates) // Sort to group duplicates var result [][]int var backtrack func(remain, start int, path []int) backtrack = func(remain, start int, path []int) { if remain == 0 { // Target reached tmp := make([]int, len(path)) copy(tmp, path) result = append(result, tmp) return } for i := start; i < len(candidates); i++ { if candidates[i] > remain { // Prune: too large break } if i > start && candidates[i] == candidates[i-1] { continue // ← Skip duplicate at same level } path = append(path, candidates[i]) // Choose backtrack(remain-candidates[i], i+1, // ← i+1: no reuse path) path = path[:len(path)-1] // Un-choose (backtrack) } } backtrack(target, 0, nil) return result }
class Solution: def combination_sum2(self, candidates: list[int], target: int) -> list[list[int]]: result: list[list[int]] = [] candidates.sort() # Sort to group duplicates self._backtrack(candidates, target, 0, [], result) return result def _backtrack(self, candidates: list[int], remain: int, start: int, path: list[int], result: list[list[int]]) -> None: if remain == 0: # Target reached result.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] > remain: # Prune: too large break if i > start and candidates[i] == candidates[i - 1]: continue # ← Skip duplicate at same level path.append(candidates[i]) # Choose self._backtrack(candidates, remain - candidates[i], i + 1, # ← i+1: no reuse path, result) path.pop() # Un-choose (backtrack)
impl Solution { pub fn combination_sum2(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> { candidates.sort(); // Sort to group duplicates let mut result = Vec::new(); Self::backtrack(&candidates, target, 0, &mut Vec::new(), &mut result); result } fn backtrack(candidates: &Vec<i32>, remain: i32, start: usize, path: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) { if remain == 0 { // Target reached result.push(path.clone()); return; } for i in start..candidates.len() { if candidates[i] > remain { // Prune: too large break; } if i > start && candidates[i] == candidates[i - 1] { continue; // ← Skip duplicate at same level } path.push(candidates[i]); // Choose Self::backtrack(candidates, remain - candidates[i], i + 1, // ← i+1: no reuse path, result); path.pop(); // Un-choose (backtrack) } } }
function combinationSum2(candidates: number[], target: number): number[][] { const result: number[][] = []; candidates.sort((a, b) => a - b); // Sort to group duplicates backtrack(candidates, target, 0, [], result); return result; } function backtrack(candidates: number[], remain: number, start: number, path: number[], result: number[][]): void { if (remain === 0) { // Target reached result.push([...path]); return; } for (let i = start; i < candidates.length; i++) { if (candidates[i] > remain) // Prune: too large break; if (i > start && candidates[i] === candidates[i - 1]) continue; // ← Skip duplicate at same level path.push(candidates[i]); // Choose backtrack(candidates, remain - candidates[i], i + 1, // ← i+1: no reuse path, result); path.pop(); // Un-choose (backtrack) } }
The two highlighted lines are the only differences from problem #39. Everything else is identical.
Enter candidates (with possible duplicates) and a target, then step through to see duplicate-skipping in action.
Each element is used at most once, so this is standard subset generation. In the worst case (all distinct candidates), we explore all 2n subsets. The duplicate-skipping rule prunes branches when there are repeated values, making it significantly faster in practice. Space is O(n) for the recursion stack depth and current path.
Generate all 2n subsets via include/exclude per element, check each subset's sum against the target, then deduplicate using a hash set. Each subset costs O(n) to hash and compare, giving O(2n × n) total work.
Sorting groups duplicates adjacently. The skip rule (i > start && candidates[i] == candidates[i-1]) prevents generating the same combination twice at the source. Combined with early-break pruning, duplicate branches are never entered, saving the O(n) hashing cost per subset.
Sorting + skip-same-value-at-same-level prevents duplicates without a hash set. The brute force would generate all subsets and deduplicate afterward (O(n) per subset for hashing). Our approach avoids generating duplicates in the first place -- each unique combination is produced exactly once.
Review these before coding to avoid predictable interview regressions.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.