Combination Sum II — LC 40 Backtracking with Duplicate Skip

Problem Statement#

Given a candidate array (with duplicates) and a target, return all unique combinations whose sum equals the target. Each candidate may be used at most once per combination.

Constraints:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

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

Input:  candidates = [2,5,2,1,2], target = 5
Output: [[1,2,2],[5]]

Why This Problem Matters#

LC 40 is a recurring array interview question at Amazon, Apple, and Microsoft. It is the natural follow-up to Combination Sum I, but the duplicate input is what trips most candidates. The problem distills three core skills: backtracking, ordered enumeration, and the same-level skip trick.

If you can crisply explain why if i > start and candidates[i] == candidates[i-1]: continue produces unique combinations, you have shown the interviewer you understand decision trees, not just code patterns. That is exactly what FAANG loop rounds want to see.

The Core Insight#

Sort the array. Now duplicates sit next to each other, and you can skip them at the same recursion level while still allowing them inside deeper levels (so [1,1,6] is fine but [1,...] and [1,...] are not produced twice from the same starting position).

The condition i > start and candidates[i] == candidates[i-1] ensures the first occurrence at this level is taken, and any subsequent identical values at this level are pruned. This is the canonical pattern for "subsets / permutations / combinations with duplicates."

Visual Dry Run#

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

Solution (Optimal)#

class Solution:
    def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()
        result = []
        path = []
 
        def backtrack(start: int, remaining: int) -> None:
            if remaining == 0:
                result.append(path.copy())
                return
            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
                if candidates[i] > remaining:
                    break
                path.append(candidates[i])
                backtrack(i + 1, remaining - candidates[i])
                path.pop()
 
        backtrack(0, target)
        return result

var combinationSum2 = function(candidates, target) {
    candidates.sort((a, b) => a - b);
    const result = [];
    const path = [];
 
    const backtrack = (start, remaining) => {
        if (remaining === 0) {
            result.push([...path]);
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] === candidates[i - 1]) continue;
            if (candidates[i] > remaining) break;
            path.push(candidates[i]);
            backtrack(i + 1, remaining - candidates[i]);
            path.pop();
        }
    };
 
    backtrack(0, target);
    return result;
};

Time: O(2^n) worst case — bounded backtracking tree. Space: O(target) recursion depth plus output.

Common Mistakes#

• Skipping duplicates with i > 0 instead of i > start, which over-prunes and loses valid combos.
• Forgetting to sort first; the duplicate-skip rule depends on adjacency.
• Using i instead of i + 1 on the recursive call, which lets a candidate be reused.
• Mutating path and pushing it directly instead of a copy.
• Continuing iteration after candidates[i] > remaining — sorted input lets you break.

Interview Tips#

• Sort early and explain the duplicate-skip invariant in plain English.
• Use the early break once candidates[i] > remaining for a real speedup.
• Walk through one duplicate skip explicitly so the interviewer sees it in action.
• Mention space: recursion stack is O(target) since each step subtracts at least 1.

Follow-up Questions#

• What if numbers can be reused infinitely? That is LC 39, recurse with i not i + 1.
• Negative numbers in candidates? You lose the break and need explicit pruning.
• Count combinations only — switch to DP, O(target * n).
• Largest combination by sum or length — add a tracking variable.
• Stream of candidates — buffer until you can sort.

Key Takeaways#

• Sort the input so duplicates are adjacent and pruning works.
• Use i > start (not i > 0) to skip same-level repeats only.
• Recurse with i + 1 to enforce one-time use per combination.
• Early break on candidates[i] > remaining gives big speedups.
• Always push a copy of the path to the result list.
• Time is exponential in the worst case, polynomial when target is small.
• Same template handles LC 39, 40, 78, 90, 46, 47.