Combination Sum

MEDIUM✓ CHIP-TIMEDLC #39 — FULL STATEMENT ↗

The drill: Pick numbers from a list, reusing any number as many times as needed, so the picks add up exactly to a target — return every distinct way to do it (order inside a pick doesn't matter).

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A list of candidate numbers and a target arrive together. The drill is to pick numbers from the list — the same number reusable as many times as it fits — so the chosen numbers add up exactly to the target.

Reuse is unlimited: one candidate can appear in a single combination two, three, or more times, as long as the running sum never passes the target and eventually lands on it exactly.

Two combinations count as the same result only when they hold the same numbers the same number of times — the order the numbers were picked in doesn't create a new combination, so each valid multiset is reported once.

EX 01

candidates = [2, 3, 6, 7] · target = 7

→ [[2, 2, 3], [7]]

TWO DISTINCT WAYS

EX 02

candidates = [2, 3, 5] · target = 8

→ [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

ONE CANDIDATE REUSED FOUR TIMES

EX 03

candidates = [2] · target = 1

→ []

NO CANDIDATE SMALL ENOUGH — EMPTY RESULT

candidates are distinct positive numbers, roughly a few dozen at most
target is a positive integer, generally kept small enough to keep recursion fast
any candidate may be reused any number of times within one combination
combinations are unique by multiset — picking order never produces a duplicate

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Reuse is allowed, so this isn't a simple 'choose k' problem — the same number can appear in one pick as many times as it fits. The real risk is counting the same multiset of numbers twice, once per ordering.

HINT 2 THE STRUCTURE

Once you decide to never look backward past a number you've already moved beyond, every multiset can only be built in one ascending order — permutations of the same numbers collapse into a single path.

HINT 3 ONE STEP FROM THE ANSWER

Backtrack with a start index. At each step either take candidates[start] again (recurse without moving start) or move to start + 1. Sort first so you can break the loop the moment the running sum would overshoot.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE OVERSHOOT PRUNEPATTERN · SORTED BACKTRACK, START INDEXcandidates = [2, 3] · target = 5

STEP 1

Candidates sorted: 2 then 3. Target 5. A candidate may repeat, but the loop only ever moves forward, so no multiset is ever built twice.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/combination-sum.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def combinationSum(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)):
                c = candidates[i]
                if c > remaining:            # sorted — nothing further can fit either
                    break
                path.append(c)
                backtrack(i, remaining - c)  # i, not i + 1 — this candidate may repeat
                path.pop()

        backtrack(0, target)
        return res

TIME O(2ᵗᵃʳᵍᵉᵗ)SPACE O(TARGET)PYTHON · RACE PACE · 20 LN

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        results = set()
        path = []

        def backtrack(remaining):
            if remaining == 0:
                results.add(tuple(sorted(path)))
                return
            if remaining < 0:
                return
            for c in candidates:            # any candidate, any order — permutations collide later
                path.append(c)
                backtrack(remaining - c)
                path.pop()

        backtrack(target)
        return [list(t) for t in results]

TIME O(Nᵗᵃʳᵍᵉᵗ)SPACE O(TARGET)PYTHON · TRAINING PACE · 18 LN

class Solution {
    public List<List<Integer>> combinationSum(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 (candidates[i] > remaining) {
                break;
            }
            path.add(candidates[i]);
            backtrack(candidates, i, remaining - candidates[i], path, res);
            path.remove(path.size() - 1);
        }
    }
}

TIME O(2ᵗᵃʳᵍᵉᵗ)SPACE O(TARGET)JAVA · RACE PACE · 23 LN

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Set<List<Integer>> results = new HashSet<>();
        backtrack(candidates, target, new ArrayList<>(), results);
        return new ArrayList<>(results);
    }

    private void backtrack(int[] candidates, int remaining, List<Integer> path, Set<List<Integer>> results) {
        if (remaining == 0) {
            List<Integer> sorted = new ArrayList<>(path);
            Collections.sort(sorted);
            results.add(sorted);
            return;
        }
        if (remaining < 0) {
            return;
        }
        for (int c : candidates) {
            path.add(c);
            backtrack(candidates, remaining - c, path, results);
            path.remove(path.size() - 1);
        }
    }
}

TIME O(Nᵗᵃʳᵍᵉᵗ)SPACE O(TARGET)JAVA · TRAINING PACE · 24 LN

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