#39 Combination Sum

frequently reported atWalmart ByteDance / TikTok Airbnb Amazon Microsoft Uber

the problem

In plain words

Given distinct positive candidates and a target, return all unique combinations that sum to target. Each candidate may be used any number of times. Two combinations are the same if they use the same numbers the same number of times.

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

out [[2,2,3],[7]]

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

out [[2,2,2,2],[2,3,3],[3,5]]

in candidates = [2], target = 1

out []

1 ≤ candidates.length ≤ 30
2 ≤ candidates[i] ≤ 40, all distinct
1 ≤ target ≤ 40

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBacktracking: combinations & partitions

Recurse with i (not i + 1) to allow reuse, and keep start so [2,3] and [3,2] aren't both produced. Sorting lets one break cut every larger candidate.

solutions

From brute force to optimal

At index i either take c[i] (stay on i) or move past it for good. Stop when remain hits 0 or goes negative.

remain == 0 → record.
i == n or remain < 0 → return.
Take c[i]: recurse(i, remain − c[i]); undo.
Skip c[i]: recurse(i + 1, remain).

timeO(2^(T/M + n))

Rough bound: up to T/M takes plus n skips along any root-to-leaf path (T = target, M = smallest candidate); no branch is cut early.

spaceO(T/M + n)

Recursion depth: every take or skip adds a frame.

javajava.util.*

1class Solution {2    public List<List<Integer>> combinationSum(int[] candidates, int target) {3        List<List<Integer>> result = new ArrayList<>();4        dfs(candidates, 0, target, new ArrayList<>(), result);5        return result;6    }7 8    private void dfs(int[] c, int i, int remain, List<Integer> path, List<List<Integer>> result) {9        if (remain == 0) {10            result.add(new ArrayList<>(path));11            return;12        }13        if (i == c.length || remain < 0) return;  // ran out of numbers, or overshot14        path.add(c[i]);                           // pick c[i] and STAY on i (it may be reused)15        dfs(c, i, remain - c[i], path, result);16        path.remove(path.size() - 1);17        dfs(c, i + 1, remain, path, result);      // skip c[i] for good18    }19}

Sort. At each node loop i from start; if c[i] > remain, break — every later candidate is too big too.

Sort candidates.
remain == 0 → record a copy.
For i from start: if c[i] > remain break.
Choose c[i], recurse(i, remain − c[i]), un-choose.

timeO(N^(T/M + 1))

Each node has ≤ N children and depth ≤ T/M (LeetCode editorial bound); pruning removes most of it in practice.

spaceO(T/M)

The deepest path uses the smallest candidate T/M times.

javajava.util.*

1class Solution {2    public List<List<Integer>> combinationSum(int[] candidates, int target) {3        Arrays.sort(candidates); // small first → we can stop early4        List<List<Integer>> result = new ArrayList<>();5        backtrack(candidates, 0, target, new ArrayList<>(), result);6        return result;7    }8 9    private void backtrack(int[] c, int start, int remain, List<Integer> path, List<List<Integer>> result) {10        if (remain == 0) {11            result.add(new ArrayList<>(path));12            return;13        }14        for (int i = start; i < c.length; i++) {15            if (c[i] > remain) break; // sorted: everything after is too big too16            path.add(c[i]);17            backtrack(c, i, remain - c[i], path, result); // i, not i+1: reuse allowed18            path.remove(path.size() - 1);19        }20    }21}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public List<List<Integer>> combinationSum(int[] candidates, int target) {3        Arrays.sort(candidates); // small first → we can stop early4        List<List<Integer>> result = new ArrayList<>();5        backtrack(candidates, 0, target, new ArrayList<>(), result);6        return result;7    }8 9    private void backtrack(int[] c, int start, int remain, List<Integer> path, List<List<Integer>> result) {10        if (remain == 0) {11            result.add(new ArrayList<>(path));12            return;13        }14        for (int i = start; i < c.length; i++) {15            if (c[i] > remain) break; // sorted: everything after is too big too16            path.add(c[i]);17            backtrack(c, i, remain - c[i], path, result); // i, not i+1: reuse allowed18            path.remove(path.size() - 1);19        }20    }21}

in the room

How to say it in the interview

talk track

Clarify: reuse allowed, numbers distinct and positive (positivity is what makes pruning valid).
"Recurse with i to allow reuse; start keeps combinations in non-decreasing order so there are no duplicates."
Mention the DP alternative if they only want the count (Coin Change II / Combination Sum IV differ on whether order matters).

traps

Recursing with i + 1 (no reuse) or 0 (duplicate orderings).
Using continue instead of break after sorting — correct but wastes the pruning.

what they ask next

Follow-ups

Each number used at most once, with duplicates (LC 40)?

Recurse with i + 1 and skip equal neighbours at the same depth — see Combination Sum II.

What if candidates could be negative?

The search may never terminate (add +x and −x forever). You'd need a bound on length; the problem forbids it for that reason.

before you submit

Edge cases to test

No combination works ([2], target 1) → [].
The target is reached only by repeating one number: [3], target 9 → [[3, 3, 3]].
Candidates arrive unsorted: sort first, or the break cuts real answers.

practise next