Combination Sum II LeetCode 40 Guide

Combination Sum II (LeetCode 40) gives you a candidates array that may contain duplicate values and a target integer. Your task is to find all unique combinations of candidates that sum exactly to the target, where each candidate may only be used once in a combination.

Unlike its predecessor Combination Sum I, the input array here can have duplicates — for example, two 1s in the candidates list. This changes the problem fundamentally: you must avoid producing the same combination twice even though the raw input contains repeated values.

The constraint that makes this problem tricky is dual: you cannot reuse an element (unlike Problem 39), and you cannot produce duplicate combinations even when the input has repeated values. Getting both constraints right simultaneously is the central challenge.

In Combination Sum I (LeetCode 39), elements can be reused as many times as needed. The backtracking call passes the same index: recurse(i, remaining - nums[i]). Because you stay at index i, you can pick the same element again on the next level.

In Combination Sum II, each element is used at most once. The fix for reuse is straightforward: pass i+1 instead of i so the next level starts after the current element. But that alone is insufficient — the input can have duplicates, and naively picking nums[i] at position 0 and nums[i] at position 1 (when both equal 1) produces identical combinations.

Sorting the candidates is the enabling step. Once sorted, duplicate values are adjacent. You can then detect at the same recursion level whether you are about to explore a value that was already explored from this position — and skip it. This is the complete solution: sort, pass i+1, and skip adjacent duplicates at the same level.

The algorithm begins by sorting candidates in non-decreasing order. Sorting serves two purposes: it enables the adjacent-duplicate skip condition, and it enables early termination — once a candidate exceeds the remaining target, all subsequent candidates will too, so you can break instead of continue.

The backtrack function takes three parameters: start (the index to begin choosing from), remaining (how much target is still needed), and path (the current combination being built). The base case is remaining == 0, meaning the current path sums to target and should be added to results.

For each index i from start to n-1, apply the skip condition first: if i > start and nums[i] == nums[i-1], skip this index. Then if nums[i] > remaining, break entirely. Otherwise, append nums[i] to path, recurse with (i+1, remaining-nums[i]), and backtrack by removing the last element.

The condition i > start and nums[i] == nums[i-1] is precise. The i > start part means we are not at the first choice position for this recursion level. The nums[i] == nums[i-1] part means the current value equals the previous value. Together: we are at the same level and this exact value was already explored from this position.

When i == start, it is the first choice at this level — it is always valid to pick it regardless of what value nums[i] holds. The skip only fires for subsequent positions at the same level where the same value has already been tried.

Removing the i > start guard would incorrectly skip valid first choices. For example, if the first candidate at some level is 1 and the previous call also ended on 1, you would wrongly skip a legitimate starting point. The guard ensures correctness while still eliminating all true duplicates.

Take candidates = [10, 1, 2, 7, 6, 1, 5] and target = 8. After sorting: [1, 1, 2, 5, 6, 7, 10]. The two 1s are now adjacent, setting up the duplicate skip.

Starting from index 0, the first branch picks nums[0] = 1 (remaining = 7). From there it picks nums[1] = 1 (remaining = 6), then tries nums[2] = 2, ..., eventually finds [1, 1, 6]. It also finds [1, 2, 5] and [1, 7] along this branch. When the loop reaches index 1 (the second 1) with i > 0 = start and nums[1] == nums[0], it skips — preventing a duplicate [1, ...] branch at the top level.

The final results are [1, 1, 6], [1, 2, 5], [1, 7], and [2, 6]. Notice there is no [1, 1, 6] appearing twice even though there are two 1s in the input — that is the skip condition doing its job correctly.

In Python, sort candidates with candidates.sort(), define results = [] outside, and write backtrack(start, remaining, path). The loop is for i in range(start, len(candidates)). The skip is if i > start and candidates[i] == candidates[i-1]: continue. The prune is if candidates[i] > remaining: break. Otherwise: path.append, backtrack(i+1, remaining-candidates[i], path), path.pop().

In Java, Arrays.sort(candidates) first. Inside the recursive method, use a for loop with the same i > start duplicate check and the remaining < candidates[i] break. Use a LinkedList as the path and add/removeLast for O(1) operations at both ends. Add new ArrayList<>(path) to results when remaining == 0.

Time complexity is O(2^n) in the worst case — each element is either included or excluded. In practice, the sort+break pruning eliminates large portions of the search tree when candidates have many values larger than the remaining target. Space complexity is O(n) for the recursion stack depth, where n is the number of candidates.

Combination Sum I (LeetCode 39) is the natural predecessor — same structure but elements can be reused. If you understand Problem 40, Problem 39 is simpler: remove the duplicate skip and pass i instead of i+1. The sort-and-break pruning still applies and is equally effective.

Subsets II (LeetCode 90) uses the identical duplicate-skipping pattern. The only difference is that every path is valid (not just those summing to target), so there is no remaining parameter and no base case check beyond the loop itself. Mastering one makes the other trivial.

Permutations (LeetCode 46) and Permutations II (LeetCode 47) are the corresponding permutation problems — same backtracking family, different structural constraint (order matters, visited array instead of start index). The duplicate-handling in Permutations II echoes the skip condition here. Recognizing this backtracking-with-duplicates family as a unified pattern is a high-leverage interview skill.