Combination Sum II

MEDIUM✓ CHIP-TIMEDLC #40 — FULL STATEMENT ↗

The drill: From a list that may repeat values, pick a subset — each position usable at most once — that sums exactly to a target. Return every distinct combination of values, with no repeats even when duplicate numbers make the same combination reachable multiple ways.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A list of numbers that may include duplicates, plus a target, arrive together. The task is to pick a subset of positions — each position usable at most once — whose values sum exactly to the target.

Because the same value can sit at more than one position, two different position-subsets can land on the exact same list of values. Only one copy of any such combination belongs in the final answer.

A combination is a plain list of values, and what makes two combinations 'the same' is having identical values in some order — position doesn't matter, only the multiset of values chosen.

EX 01

candidates = [3, 1, 3, 5, 1, 1] · target = 6

→ [[1, 1, 1, 3], [1, 5], [3, 3]]

DUPLICATES EVERYWHERE

EX 02

candidates = [5] · target = 5

→ [[5]]

MINIMUM SIZE, EXACT MATCH

EX 03

candidates = [5] · target = 3

→ []

NO WAY TO REACH THE TARGET

candidate values can repeat; each individual position is still usable only once
candidates and target are positive numbers, kept modest in size
duplicate combinations of values must never appear twice in the output
combinations are compared as multisets, not as ordered lists

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Every number can be used once, but the same VALUE can sit at multiple positions — two different index-subsets can produce the identical list of values. That's the trap, not the recursion itself.

HINT 2 THE STRUCTURE

Sort the array first. Duplicate values become neighbors, and a duplicate combination only forms when a repeated value is picked as something other than the FIRST choice at a given recursion depth.

HINT 3 ONE STEP FROM THE ANSWER

Backtrack with a start index, each index usable once. At each depth, skip candidates[i] if it equals candidates[i − 1] and i isn't the first choice tried at this depth — that guard removes every duplicate combination before it's built.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE SKIP-THE-TWIN PRUNEPATTERN · SORTED BACKTRACK, SKIP TWINScandidates = [2, 2, 4, 4] · target = 6

STEP 1

Candidates sorted: 2, 2, 4, 4. Target 6. Each index is used at most once, and a value repeated at the same depth is skipped so no duplicate combination is built.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/combination-sum-ii.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        res = []
        path = []

        def backtrack(start, remaining):
            if remaining == 0:
                res.append(list(path))
                return
            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i - 1]:
                    continue  # same value already tried at this depth
                c = candidates[i]
                if c > remaining:
                    break
                path.append(c)
                backtrack(i + 1, remaining - c)
                path.pop()

        backtrack(0, target)
        return res

TIME O(2ⁿ)SPACE O(N)PYTHON · RACE PACE · 22 LN

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        n = len(candidates)
        found = set()
        for mask in range(1 << n):
            total = 0
            combo = []
            for i in range(n):
                if mask & (1 << i):
                    total += candidates[i]
                    combo.append(candidates[i])
            if total == target:
                found.add(tuple(sorted(combo)))
        return [list(t) for t in found]

TIME O(N·2ⁿ)SPACE O(N)PYTHON · TRAINING PACE · 14 LN

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(candidates, 0, target, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] candidates, int start, int remaining, List<Integer> path, List<List<Integer>> res) {
        if (remaining == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (candidates[i] > remaining) {
                break;
            }
            path.add(candidates[i]);
            backtrack(candidates, i + 1, remaining - candidates[i], path, res);
            path.remove(path.size() - 1);
        }
    }
}

TIME O(2ⁿ)SPACE O(N)JAVA · RACE PACE · 26 LN

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int n = candidates.length;
        Set<List<Integer>> found = new HashSet<>();
        for (int mask = 0; mask < (1 << n); mask++) {
            int total = 0;
            List<Integer> combo = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    total += candidates[i];
                    combo.add(candidates[i]);
                }
            }
            if (total == target) {
                Collections.sort(combo);
                found.add(combo);
            }
        }
        return new ArrayList<>(found);
    }
}

TIME O(N·2ⁿ)SPACE O(N)JAVA · TRAINING PACE · 21 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED