72.Combination Sum

MediumBlind 75Backtracking · 2/9

Problem

Given an array of distinct positive integers candidates and an integer target, return all unique combinations of candidates whose numbers sum to target.

The same number may be chosen an unlimited number of times. Two combinations are the same if they use the same numbers with the same frequencies, regardless of order, so [2,2,3] and [3,2,2] count once.

Examples

Input:  candidates = [2, 3, 6, 7], target = 7
Output: [[2,2,3], [7]]
Explanation: 2 + 2 + 3 = 7 and 7 = 7. No other multiset works.

Input:  candidates = [2, 3, 5], target = 8
Output: [[2,2,2,2], [2,3,3], [3,5]]

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

Constraints

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40

💡 Key Insight

To avoid duplicate orderings, only ever pick candidates at index >= start: once you move past a candidate you never come back to it. Because reuse is allowed, after picking candidates[i] you recurse with the same i. Sorting first lets you stop the loop as soon as a candidate exceeds the remaining target.

Brute Force (Include / Skip)

TimeO(2^(t/m)) roughly, where t = target and m = smallest candidateSpaceO(t/m)

Intuition

Treat it like Subsets with repetition: at index i either take candidates[i] again (stay at i) or move on to i + 1. Stop when the remaining sum is 0 (record it) or negative / out of candidates (dead end). Without sorting there is no early cut-off, so many dead branches are explored.

Algorithm

dfs(i, remaining):
- If remaining == 0, record a copy of path.
- If remaining < 0 or i == n, return.
Take: push candidates[i], dfs(i, remaining - candidates[i]), pop.
Skip: dfs(i + 1, remaining).

Visualization

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

take 2 -> take 2 -> take 2 -> rem=1 -> take 2 -> rem=-1  dead
                              rem=1 -> skip to 3 -> rem=-2 dead ...
take 2 -> take 2 -> skip 2 -> take 3 -> rem=0   record [2,2,3]
skip 2 -> skip 3 -> skip 6 -> take 7 -> rem=0   record [7]

Code

java

import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(candidates, 0, target, new ArrayList<>(), result);
        return result;
    }

    private void dfs(int[] cand, int i, int remaining, List<Integer> path, List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        if (remaining < 0 || i == cand.length) {
            return; // overshot or ran out of candidates
        }
        path.add(cand[i]);                          // take cand[i] (may take it again)
        dfs(cand, i, remaining - cand[i], path, result);
        path.remove(path.size() - 1);
        dfs(cand, i + 1, remaining, path, result);  // move to the next candidate
    }
}

Complexity

Time: O(2^(t/m)) roughly, where t = target and m = smallest candidate — the tree depth is at most t/m and each node branches twice.
Space: O(t/m) — recursion depth.

Sorted Backtracking with PruningOptimal

TimeO(n^(t/m)) worst caseSpaceO(t/m)

Intuition

Use a for loop over choices instead of take/skip: at each level, try every candidate from start onward and recurse with the same index (reuse allowed). Sort candidates first; when candidates[i] > remaining, every later candidate is even bigger, so break the loop instead of recursing into hopeless branches.

Algorithm

Sort candidates.
backtrack(start, remaining):
- If remaining == 0, record a copy of path.
- For i from start to n - 1:
  - If candidates[i] > remaining, break.
  - Push candidates[i], backtrack(i, remaining - candidates[i]), pop.

Visualization

flowchart TD
    R["rem=7 []"] -->|"2"| A["rem=5 [2]"]
    R -->|"3"| B["rem=4 [3]"]
    R -->|"7"| C["rem=0 [7] ✓"]
    A -->|"2"| A1["rem=3 [2,2]"]
    A -->|"3"| A2["rem=2 [2,3]"]
    A1 -->|"2"| A11["rem=1 [2,2,2]<br/>2 > 1 break"]
    A1 -->|"3"| A12["rem=0 [2,2,3] ✓"]
    A2 -->|"3 > 2"| A21["break"]
    B -->|"3"| B1["rem=1 [3,3]<br/>3 > 1 break"]
    B -->|"6 > 4"| B2["break"]

Code

java

import java.util.*;

class Solution {
    private final List<List<Integer>> result = new ArrayList<>();
    private final List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates); // enables the early break
        backtrack(candidates, 0, target);
        return result;
    }

    private void backtrack(int[] cand, int start, int remaining) {
        if (remaining == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < cand.length; i++) {
            if (cand[i] > remaining) {
                break; // sorted: every later candidate is too big as well
            }
            path.add(cand[i]);
            backtrack(cand, i, remaining - cand[i]); // i, not i + 1: reuse allowed
            path.remove(path.size() - 1);
        }
    }
}

Complexity

Time: O(n^(t/m)) worst case — up to n branches per level and depth t/m; pruning removes most of it in practice.
Space: O(t/m) — recursion depth and path.

Complexity Comparison

Approach	Time	Space
Include / Skip	O(2^(t/m))	O(t/m)
Sorted Backtracking + Pruning	O(n^(t/m)) worst, heavily pruned	O(t/m)

Common Pitfalls

Recursing with i + 1 after picking — that forbids reuse and misses [2,2,3].
Restarting the loop from 0 instead of start — produces permutations like [2,3,2] and [3,2,2] as duplicates.
Using break without sorting first — you would skip valid larger-index candidates that happen to be smaller.
Storing path directly in result instead of a copy.