Combination Sum II — Solution

Problem

Given a list of candidate integers that may contain duplicates and a target value, find every unique combination of numbers from the list that adds up exactly to target. Each number from the input may only be used once per combination, and the output must not contain duplicate combinations.

• Input: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
• Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
• Explanation: All four groups sum to 8; even though there are two 1s in the input, [1,7] appears only once in the output.

Counter-example: [1,2,5] and [2,1,5] are the same combination — order does not matter, so only one version is returned.

Intuition

The core challenge is that duplicate values in the input can produce identical combinations through different index paths. Sorting the candidates first puts duplicates side-by-side; then during backtracking, if we see the same value as the one we just tried at the same decision level, we skip it — this prunes entire duplicate subtrees without needing a set.

Solution — Backtracking with Sorted Duplicate Skip

Sort candidates so duplicates are adjacent, then use a recursive helper that builds combinations one element at a time. At each level, skip any value that is equal to the previous value tried at that same level to avoid generating the same combination twice.

1. Sort candidates in ascending order.
2. Call backtrack(start=0, current=[], remaining=target).
3. If remaining == 0, append a copy of current to results and return.
4. Loop i from start to end of candidates:
   • If i > start and candidates[i] == candidates[i-1], skip — same value already explored at this level.
   • If candidates[i] > remaining, break — array is sorted so no later element can work either.
   • Append candidates[i], recurse with (i+1, current, remaining - candidates[i]), then pop.

1from typing import List
2
3class Solution:
4    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
5        candidates.sort()
6        results = []
7
8        def backtrack(start: int, current: List[int], remaining: int):
9            if remaining == 0:
10                results.append(list(current))  # copy — not the mutable reference
11                return
12            for i in range(start, len(candidates)):
13                # same value already tried at this decision level — skip entire subtree
14                if i > start and candidates[i] == candidates[i - 1]:
15                    continue
16                # sorted array: every later element is also too large
17                if candidates[i] > remaining:
18                    break
19                current.append(candidates[i])
20                backtrack(i + 1, current, remaining - candidates[i])
21                current.pop()
22
23        backtrack(0, [], target)
24        return results

Time: O(n · 2^n) — in the worst case every subset is explored (all distinct elements), and each valid combination takes O(n) to copy; duplicates and pruning make real-world performance much better.

Space: O(n) — recursion depth is at most n (using each element once), plus O(n) for the current path; result storage is not counted in auxiliary space.

Complexity Summary

Common Mistakes

• Using i > 0 instead of i > start for the duplicate guard — i > 0 skips the second occurrence of a value even when it appears at a fresh recursion level, causing valid combinations to be missed; i > start restricts the skip to the current decision level only.
• Forgetting to sort before the duplicate check — candidates[i] == candidates[i-1] only skips true duplicates when identical values are adjacent; an unsorted array can have the same value scattered, so the guard silently misses duplicates.
• Passing i instead of i+1 to the recursive call — this allows the same element to be reused (that's Combination Sum I behavior); passing i+1 enforces the "each element used at most once" rule.
• Using continue instead of break when candidates[i] > remaining — since the array is sorted, every element from index i onward is also too large, so continue wastes time checking them while break exits immediately.
• Appending current by reference instead of copying — all entries in results end up pointing to the same list object, which is empty after backtracking completes; list(current) / new ArrayList<>(current) captures the state at that moment.

Related Problems

• subsets — same backtracking skeleton; collects every path instead of only those summing to a target
• subsets-ii — uses the identical sorted-array duplicate-skip technique to avoid repeated subsets
• permutations — backtracking over ordered arrangements; uses a "used" boolean array instead of an index to track remaining choices
• letter-combinations-of-a-phone-number — backtracking over a decision tree where each level has a different set of choices
• palindrome-partitioning — backtracking with pruning based on a validity check at each cut point