Combination Sum

MediumBacktracking · Unbounded Choices🧩 Backtracking LeetCode #39 ↗Updated Oct 30, 2026

Problem

You are given an array of distinct positive integers candidates and a target. Return every unique multiset of candidates whose sum equals target; any candidate may be used any number of times. Two combinations are the same if they use the same numbers with the same counts, regardless of order.

Inputcandidates = [2,3,6,7], target = 7Output[[2,2,3],[7]]

Inputcandidates = [2,3,5], target = 8Output[[2,2,2,2],[2,3,3],[3,5]]

Inputcandidates = [4], target = 3Output[]

1 ≤ n ≤ 30 · 2 ≤ candidates[i] ≤ 40, all distinct · 1 ≤ target ≤ 40 · fewer than 150 answers

Try it yourself

Java

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Build each combination in non-decreasing index order: after choosing candidates[i], the next pick may be i again but never an earlier index. Every multiset then has exactly one path — no duplicates to filter.

PatternBacktracking

Instinct Return ALL combinations, permutations, partitions or placements - or ask if any arrangement works - build a candidate step by step and undo each choice.

Memory hack Choose, explore, un-choose - walk the decision tree and snip a branch the moment it can no longer succeed.

Open the Backtracking guide →

Approaches

Brute ForceAll Orderings + Set Dedup

Time O(n^T/m · T/m)Space O(n^T/m · T/m)

At every step try every candidate, so all ordered sequences that hit the target are found ([2,2,3], [2,3,2], [3,2,2], …). Sort each hit and drop it in a Set to collapse orderings into one multiset. Here T = target and m = smallest candidate (max depth T/m).

Java

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Set<List<Integer>> seen = new HashSet<>();
    explore(candidates, target, new ArrayList<>(), seen);
    return new ArrayList<>(seen);
}
private void explore(int[] c, int remain, List<Integer> path, Set<List<Integer>> seen) {
    if (remain == 0) {
        List<Integer> key = new ArrayList<>(path);
        Collections.sort(key); // orderings of one multiset share a key
        seen.add(key);
        return;
    }
    if (remain < 0) return;
    for (int x : c) { // any candidate, in any order
        path.add(x);
        explore(c, remain - x, path, seen);
        path.remove(path.size() - 1);
    }
}

Works, but a k-element answer is generated up to k! times and needs a set.

BetterBacktracking with Start Index

Time O(n^T/m)Space O(T/m)

Pass a start index: the loop only offers candidates[start..], and recursing with the same i allows reuse. Paths are forced into index order, so each multiset is built exactly once and no set is needed. Branches stop only once remain goes negative.

Java

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(candidates, 0, target, new ArrayList<>(), res);
    return res;
}
private void backtrack(int[] c, int start, int remain, List<Integer> path,
                       List<List<Integer>> res) {
    if (remain == 0) {
        res.add(new ArrayList<>(path));
        return;
    }
    if (remain < 0) return; // overshot
    for (int i = start; i < c.length; i++) {
        path.add(c[i]);
        backtrack(c, i, remain - c[i], path, res); // i, not i + 1: reuse allowed
        path.remove(path.size() - 1);
    }
}

No duplicates, O(depth) extra space; still walks into dead branches one step too far.

OptimalSorted Backtracking with Early Break

Time O(n^T/m)Space O(T/m)

Sort the candidates first. Inside the loop, once candidates[i] > remain every later candidate is larger too, so break the whole loop instead of recursing into hopeless branches. The worst-case bound is unchanged, but the search tree shrinks dramatically.

Java

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    int[] c = candidates.clone();
    Arrays.sort(c); // enables the early break
    List<List<Integer>> res = new ArrayList<>();
    backtrack(c, 0, target, new ArrayList<>(), res);
    return res;
}
private void backtrack(int[] c, int start, int remain, List<Integer> path,
                       List<List<Integer>> res) {
    if (remain == 0) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i < c.length; i++) {
        if (c[i] > remain) break; // sorted: nothing after fits either
        path.add(c[i]);
        backtrack(c, i, remain - c[i], path, res);
        path.remove(path.size() - 1);
    }
}

Same output with far fewer calls — the standard interview answer.

Pro tip

Contrast with Combination Sum II: there you recurse with i + 1 and skip equal neighbours; here you recurse with i.

At a glance

Level	Approach	Time	Space
Brute Force	All Orderings + Set Dedup	`O(n^T/m · T/m)`	`O(n^T/m · T/m)`
Better	Backtracking with Start Index	`O(n^T/m)`	`O(T/m)`
Optimal	Sorted Backtracking with Early Break	`O(n^T/m)`	`O(T/m)`

Common pitfalls

Recursing with i + 1 — forbids reusing a number, missing [2,2,3].
Restarting the loop at 0 each call — produces [2,3,2] and [3,2,2] as duplicates.
Adding path itself instead of a copy — every answer ends up empty.

Interview tips

Draw the decision tree for [2,3,6,7] / 7 and show where index order kills duplicates.
Explain the bound: depth ≤ target / smallest candidate.
Mention the sort + break pruning as the cheap, big practical win.

Pattern

Backtracking with a start index → enumerate combinations (not permutations) of items that sum to a target.

My notes saved in this browser