Combination Sum II: Backtracking Without Duplicates

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. The solution set must not contain duplicate combinations.

This is LeetCode 40: Combination Sum II, and it builds directly on Combination Sum. The twist is that candidates can contain duplicates (like [1, 1, 2, 5, 6, 7, 10]), and each element can only be used once. Without careful handling, you will produce duplicate result sets. The fix is a single guard clause that skips same-level duplicates after sorting.

Why this problem matters

Combination Sum II teaches you the most important deduplication technique in backtracking: same-level duplicate skipping. In Combination Sum, all candidates are distinct and reuse is allowed, so duplicates never arise. In Subsets, all elements are unique, so there is nothing to skip. Combination Sum II is the first problem where you face both duplicate elements and a "use each at most once" constraint. The skill you learn here applies to Subsets II, Permutations II, and any backtracking problem with repeated input values.

The problem also reinforces the connection between sorting and pruning. Sorting the candidates does two things at once: it groups equal values together (so you can detect and skip duplicates) and it lets you break early when a candidate exceeds the remaining target. These two optimizations are separate ideas, but they both depend on the array being sorted.

The key insight

Sort the candidates first. Then, when iterating over choices at a given recursion level, skip any candidate that equals the previous candidate at that same level. The check is: if candidates[i] == candidates[i - 1] and i > start, skip candidates[i].

Why does this work? Consider sorted input [1, 1, 2, 5, 6, 7, 10] with target 8. At the root level, you try the first 1 at index 0. That recursive call explores everything reachable by starting with 1, including paths like [1, 1, 6] where the second 1 comes from a deeper level. When you return to the root level and reach the second 1 at index 1, every combination it would produce is a subset of what the first 1 already found. So you skip it.

The critical distinction: the second 1 is only skipped when it appears at the same recursion level as the first 1. At a deeper level, using both 1s is fine because they represent different positions in the input.

The algorithm works like this:

1. Sort the candidates.
2. Start with an empty combination, remaining = target, and start index 0.
3. If remaining is 0, the current combination sums to the target. Record it.
4. For each candidate from the start index onward:
   • If the candidate exceeds remaining, break (sorted, so all later candidates are bigger).
   • If i > start and candidates[i] == candidates[i - 1], continue (skip same-level duplicate).
   • Otherwise, choose the candidate (append), explore (recurse with i + 1 and reduced remaining), and unchoose (pop).

The backtracking solution

def combinationSum2(candidates: list[int], target: int) -> list[list[int]]:
    candidates.sort()
    result = []

    def backtrack(start, remaining, current):
        if remaining == 0:
            result.append(current[:])
            return

        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break

            if i > start and candidates[i] == candidates[i - 1]:
                continue

            current.append(candidates[i])
            backtrack(i + 1, remaining - candidates[i], current)
            current.pop()

    backtrack(0, target, [])
    return result

Let's break this down.

The outer function sorts the candidates. Sorting is essential here, not just an optimization. Without sorting, you cannot detect same-level duplicates by comparing adjacent elements, and you cannot use the break pruning.

Inside backtrack, the base case is remaining == 0. When the running sum hits the target exactly, copy the current combination and add it to the result.

The for loop iterates from start to the end. Two guard clauses appear before the choose step:

First, if candidates[i] > remaining, we break. Since the array is sorted, every candidate after this one is at least as large, so none of them can work either. This prunes entire subtrees.

Second, if i > start and candidates[i] == candidates[i - 1], we continue. This is the duplicate-skipping rule. The condition i > start is important: at index start, we always try the candidate (it is the first one at this recursion level). Only when i has moved past start do we check for a duplicate. If the current candidate equals the previous one, we have already explored a subtree rooted at that same value, so we skip it.

After the guards, we append the candidate (choose), recurse with i + 1 and reduced remaining (explore), and pop it off (unchoose). Passing i + 1 instead of i is what prevents reuse of the same element.

Visual walkthrough

Let's trace through the algorithm with candidates = [10, 1, 2, 7, 6, 1, 5] and target = 8. After sorting, the candidates become [1, 1, 2, 5, 6, 7, 10]. Watch how the duplicate-skipping rule prevents the second 1 from creating a redundant subtree at the root level.

The key moment is Step 8. When the loop reaches the second 1 at index 1, the condition i > start and candidates[1] == candidates[0] is true. The algorithm skips it entirely. Without this check, the second 1 would generate the same combinations as the first 1 (like [1, 2, 5] and [1, 7]), leading to duplicate results.

Notice that [1, 1, 6] is still valid. The two 1s in that combination come from different recursion levels: the first 1 is chosen at the root level, and the second 1 is chosen one level deeper. The skip rule only blocks duplicates at the same level.

How this differs from Combination Sum I

In Combination Sum, candidates are distinct and reuse is allowed. In Combination Sum II, candidates can repeat and each can only be used once. The i + 1 handles the "once only" constraint. The i > start guard handles the "no duplicate result sets" constraint.

Complexity analysis

Time is O(2^n) in the worst case. Each element is either included or excluded, giving 2^n possible subsets. Pruning and duplicate-skipping reduce the actual work significantly in practice, but the upper bound is exponential. Sorting adds O(n log n), which is dominated by the exponential backtracking.

Space is O(n) for the recursion stack (maximum depth equals the number of candidates) plus the space for storing results. If you exclude the output, the extra space is just O(n).

The building blocks

This problem is built on two core reusable pieces that CodeBricks drills independently.

Sorted backtracking (choose-explore-unchoose with sorted input)

The same skeleton that powers Combination Sum, Subsets, and Permutations:

def backtrack(state):
    if is_solution(state):
        record(state)
        return

    for choice in candidates(state):
        make_choice(choice)
        backtrack(state)
        undo_choice(choice)

In Combination Sum II, make_choice is current.append(candidates[i]). The recursion uses i + 1 to prevent reuse. undo_choice is current.pop(). Sorting the input before calling backtrack enables both the break pruning and the duplicate detection.

Same-level duplicate skipping

The pattern for avoiding duplicate results when the input contains repeated values:

if i > start and candidates[i] == candidates[i - 1]:
    continue

This guard appears in any backtracking problem where the input has duplicates and the output must be unique. The same technique applies to Subsets II (LeetCode 90) and Permutations II (LeetCode 47). The key is that i > start ensures you only skip when you have already processed an identical value at the current recursion level.

Edge cases

Before submitting, check these:

• No valid combinations: candidates = [3, 5], target = 2. Should return []. The smallest candidate exceeds the target.
• Single candidate equals target: candidates = [8], target = 8. Should return [[8]]. One element, one combination.
• All same numbers: candidates = [2, 2, 2, 2], target = 4. Should return [[2, 2]]. Despite four copies, only one unique pair sums to 4. The duplicate-skipping prevents [2, 2] from appearing multiple times.
• Large number of duplicates: Duplicate-skipping keeps the result set small, but the sorting step must handle the full input.
• Candidate larger than target: Sorted input means break handles this immediately.

From understanding to recall

You understand the recursion tree. You see how i + 1 prevents reuse, how i > start with the equality check skips same-level duplicates, and how sorting enables both optimizations at once. But can you write the solution from scratch in under two minutes?

That is what interviews demand. The duplicate-skipping guard is easy to get wrong under pressure. Using i > 0 instead of i > start, forgetting to sort, or passing i instead of i + 1 are all common mistakes that produce wrong answers. These are not conceptual gaps. They are recall problems.

Spaced repetition fixes recall. You practice writing the sorted-backtracking template and the same-level duplicate-skipping guard from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "combination sum with duplicates" and the code flows out without hesitation.

The sorted backtracking and same-level duplicate skipping patterns are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Combination Sum - The version with unlimited reuse and distinct candidates. Compare the two to see how i vs i + 1 and the duplicate-skipping guard change the problem.
• Subsets - The simplest backtracking problem using the same choose-explore-unchoose template. Subsets II (LeetCode 90) uses the same duplicate-skipping technique as Combination Sum II.

CodeBricks breaks Combination Sum II into its sorted-backtracking and duplicate-skipping building blocks, then drills them independently with spaced repetition. You type the backtracking skeleton and the deduplication guard from scratch until they are automatic. When a backtracking-with-duplicates problem shows up in your interview, you do not think about it. You just write it.