Combination Sum II

The hard part is not finding combinations that add to the target. It is finding them once while respecting the physical number of occurrences in the input.

A backtracking tree can enforce single use and still emit duplicate value combinations. The reliable model is:

1. Sort the candidates.
2. Skip equal choices only when they are siblings at the same recursion depth.
3. Recurse from i + 1 after choosing index i.

Those three decisions solve three different problems. Sorting exposes structure, sibling skipping removes duplicate output paths, and i + 1 preserves single-use behavior.

Read the contract before choosing the pattern

The result must contain every unique combination whose values sum to target. The order of combinations does not matter, and the order inside a combination does not matter.

Two constraints create the real difficulty:

• Each array occurrence can be used at most once.
• The input can contain repeated values, but equal-valued combinations must appear only once.

That is different from the reusable-candidate version of Combination Sum. In that problem, choosing index i allows the recursive call to consider i again. Here, choosing index i consumes that occurrence, so the next search begins at i + 1.

Consider sorted candidates:

[1, 1, 2, 5, 6, 7, 10]

The two 1 values are separate occurrences. A valid combination may use both of them, as in [1, 1, 6]. But choosing the first 1 at the root and choosing the second 1 at the root lead to the same value prefix. Exploring both creates duplicate output.

This gives us the central distinction:

Equal values may be used at different depths when separate occurrences exist. Equal values should not create duplicate choices at the same depth.

The positive-value constraint is also useful. Once the candidates are sorted, if the current candidate exceeds the remaining target, every later candidate is at least as large. The loop can stop immediately.

Build the indexed search tree

Sort the candidates first. Then define the recursive state as:

backtrack(start, remaining)

The state means:

• path contains the selected candidate values.
• start is the first index still eligible for selection.
• remaining is the amount still needed to reach the target.

At each recursion level, try every index from start onward:

1. Choose candidates[i].
2. Add it to path.
3. Recurse with i + 1 and remaining - candidates[i].
4. Remove it from path before trying the next candidate.

The recursive call begins at i + 1, not i, because the chosen occurrence cannot be reused.

The success condition is direct:

remaining == 0

At that point, copy path into the answers. If the next sorted candidate is too large, stop the loop because no later value can fit.

A small state trace makes the index movement concrete:

Path	start	remaining	Choose	Child state
[]	0	8	index 0, value 1	[1], start 1, remaining 7
[1]	1	7	index 1, value 1	[1, 1], start 2, remaining 6
[1, 1]	2	6	index 4, value 6	[1, 1, 6], start 5, remaining 0
[1]	1	7	index 2, value 2	[1, 2], start 3, remaining 5
[1, 2]	3	5	index 3, value 5	[1, 2, 5], start 4, remaining 0

The path is mutable state shared across recursive calls. That is useful because append and pop are cheap, but it creates a strict cleanup obligation: every append must be paired with a pop.

Skip duplicates only among siblings

After sorting, equal values are adjacent. The duplicate rule is:

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

The comparison is relative to start, the beginning of the current recursion level.

Why does i > start matter?

Suppose the current level is considering:

[1, 1, 2, 5]
 ^
 start

Choosing the first 1 creates a branch beginning with value 1. Choosing the second 1 at the same level creates the same value prefix. Since the output contains values rather than original indices, the second branch cannot produce a new combination that the first branch does not represent.

So the second 1 is skipped as a sibling.

But after choosing the first 1, the recursive call starts at the next index. At that deeper level, the second 1 is now a legitimate choice:

root:      choose first 1
child:     choose second 1
result:    [1, 1, ...]

That is how [1, 1, 6] remains possible.

This is the part people often get wrong. A global rule such as “remove duplicate values” destroys occurrence information. If the input contains two 1s, removing one means the algorithm can no longer construct combinations that require two 1 occurrences.

The phrase skip duplicates backtracking is easy to remember, but the mechanism matters more than the phrase:

Skip equal candidates when they compete as siblings. Keep them available when recursion moves deeper and a second occurrence is required.

For example, with sorted candidates [1, 1, 2, 5]:

At one level:
choose first 1  -> explore
choose second 1 -> skip; same value prefix

Below first 1:
choose second 1 -> explore; this uses a distinct occurrence

Duplicate skipping controls how branches are generated. i + 1 controls which occurrences remain available. They are separate obligations.

From brute force to a proof

A natural baseline is to enumerate every subset of indexed occurrences, keep the subsets whose sum is the target, and deduplicate the resulting value lists afterward.

That baseline is useful as a correctness reference, but it wastes work in two ways:

• It explores branches that already exceed the target.
• It explores equal sibling choices that produce the same value combination.

The optimized search keeps the same subset-like structure while removing redundant branches.

Obligation	Mechanism
Do not reuse an occurrence	Recurse from i + 1
Do not emit duplicate value combinations	Skip equal siblings with i > start
Stop impossible positive-value branches	Sort and break when candidates[i] > remaining

The key invariant is:

At every call, path uses distinct indices smaller than start, its values are in nondecreasing order, and remaining equals the target minus the sum of path.

Why every valid combination is found

Take any valid combination. Because the candidates are sorted, its selected indices can be represented in increasing order.

At each depth, the algorithm considers the candidate value needed by that index sequence. If equal values appear before it at the same depth, the algorithm may skip those duplicate siblings. That does not remove the value sequence itself; the first equal occurrence represents that entire sibling group.

When the valid combination needs another copy of the same value, that copy appears deeper in the tree after the first occurrence has already been selected. The level-local skip does not block it.

Therefore, every valid value combination has at least one surviving search path.

Why no combination is repeated

Two paths can produce the same value combination only if they differ by choosing equal-valued occurrences in equivalent sibling positions.

The sibling guard removes that duplication: at one recursion depth, only the first occurrence of a value starts a branch. Deeper recursion can still consume later equal occurrences, but that represents a different multiplicity in the combination, not a duplicate sibling path.

Thus, the algorithm keeps one representative for each value sequence while preserving the number of available occurrences.

Dry-run duplicates and dead branches

Use the canonical-style input:

candidates = [10, 1, 2, 7, 6, 1, 5]
target = 8

After sorting:

[1, 1, 2, 5, 6, 7, 10]

The search produces:

[1, 1, 6]
[1, 2, 5]
[1, 7]
[2, 6]

At the root, the first 1 is explored. When the loop reaches the second root-level 1, this condition is true:

i > start and candidates[i] == candidates[i - 1]

That branch is skipped.

Inside the first 1 branch, however, start has moved forward. The second 1 is no longer a sibling of the first root choice; it is a deeper choice. It remains available and produces [1, 1, 6].

Now examine:

candidates = [2, 5, 2, 1, 2]
target = 5

Sorted:

[1, 2, 2, 2, 5]

The root explores 1, then the first 2 beneath it. The next two 2 values at that same depth are skipped as siblings, but the recursion can move deeper and select another 2. That constructs:

[1, 2, 2]

The root-level 2 branches also collapse into one representative, and the candidate 5 gives:

[5]

The output is therefore:

[[1, 2, 2], [5]]

Overshoot pruning

Suppose a branch has:

path = [1, 2]
remaining = 3

The next candidate is 5. Because the array is sorted, every later candidate is at least 5. None can fit into a remaining target of 3, so the loop breaks.

This is stronger than returning from only the current candidate. The sorted suffix is impossible as a whole.

Empty branches

Some recursive calls reach the end of the array without finding a solution. Others stop because the next candidate is too large. These are normal leaves in the search tree, not exceptional states.

The implementation needs only two successful or terminating conditions:

• remaining == 0: record a result.
• No candidate can be chosen: return naturally, or break when the sorted suffix is too large.

Mutable path handling

The backtracking sequence must be exact:

path.append(value)
backtrack(...)
path.pop()

When a result is found, append a copy:

results.append(path.copy())

Appending path itself would store a reference to the mutable working list. Later pops would change the stored result.

Read the state. Trace the mutation. Repair the assumption. That debugging loop catches more backtracking bugs than staring at the recursion diagram.

Implement the Combination Sum II solution in Python

Here is an interview-readable implementation:

from typing import List


def combination_sum_ii(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()

    results: List[List[int]] = []
    path: List[int] = []

    def backtrack(start: int, remaining: int) -> None:
        if remaining == 0:
            results.append(path.copy())
            return

        for i in range(start, len(candidates)):
            # Equal values at this depth create the same value prefix.
            if i > start and candidates[i] == candidates[i - 1]:
                continue

            # Candidates are sorted, so the remaining suffix cannot fit.
            if candidates[i] > remaining:
                break

            path.append(candidates[i])

            # Move past the chosen occurrence: it is single-use.
            backtrack(i + 1, remaining - candidates[i])

            path.pop()

    backtrack(0, target)
    return results

The three lines carrying most of the correctness are:

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

This is level-local duplicate skipping. Removing i > start would skip repeated values at every depth and lose valid combinations such as [1, 1, 6].

backtrack(i + 1, remaining - candidates[i])

This advances beyond the selected index. Using i here would turn the algorithm into a reusable-candidate search.

if candidates[i] > remaining:
    break

Sorting makes the remaining suffix monotonic: later values cannot become smaller. The branch can be cut safely.

I prefer structural duplicate avoidance over generating every duplicate and cleaning the results with a set. A set can remove repeated outputs, but it does not prevent redundant recursive work, and it introduces extra representation and conversion decisions. When the search tree itself can be made correct, fix the tree.

This implementation sorts the input in place. That is usually fine in an interview. If the surrounding API promises not to mutate the caller's list, sort a copy instead:

candidates = sorted(candidates)

The algorithmic reasoning stays the same.

Complexity and edge-case checks

Let n be the number of candidate occurrences.

The worst-case search remains exponential because the algorithm explores subset-like choices. A useful upper-bound description is O(2^n) search paths, with additional work to copy each emitted combination. If you account for output copying directly, total runtime can be expressed as:

O(2^n + output_size)

or more conservatively as O(2^n * n) when each result may contain up to n values and path copying is included.

Sorting adds:

O(n log n)

but does not change the exponential worst-case behavior. It makes duplicate grouping and early stopping possible, which can dramatically reduce the branches actually explored.

Auxiliary space is O(n) for the recursion stack and mutable path, excluding the returned result collection. The output itself may contain many combinations, so it should not be folded into that auxiliary-space claim.

Test the boundaries deliberately:

Case	What it checks
No combination reaches the target	Empty result handling
One candidate equals the target	Immediate success
Every value is repeated	Sibling skipping
Enough copies exist to require [x, x]	Deeper duplicate selection
A candidate is larger than the target	Sorted early break
Search reaches the end of the array	Clean empty branch
Same values can be reached through different indices	Unique output semantics
A branch needs repeated values	Occurrence limits are preserved

Two implementation checks catch most plausible-looking failures:

• Confirm the recursive call uses i + 1, not i.
• Confirm duplicate skipping compares against the current start, not against the entire search globally.

The recognition rule

When a problem asks for unique combinations from duplicate-bearing input and each occurrence is single-use, do not memorize a code template. Re-derive the three decisions:

1. Sort so equal values become adjacent and oversized suffixes can be pruned.
2. Skip equal siblings only at the current depth so duplicate value paths collapse without removing valid multiplicities.
3. Recurse from i + 1 so selecting an occurrence consumes it.

That is the reusable pattern. Equal values are a question of output identity; advancing the index is a question of resource consumption. Keep those ideas separate, and the search tree becomes straightforward to build, inspect, and defend in an interview.