Command Palette

Search for a command to run...

Hectal
Problem 13.4 · BacktrackingMedium

Combination Sum

PatternBacktrackingKnapsack DP

What it teaches: Reusable elements (recurse with i, not i + 1) and pruning with a sorted array.

Practise it on judges as “Combination Sum”.

The problem

Given distinct positive candidates and a target, return all unique combinations that sum to target. Each number may be used any number of times.

Example 1

Input: candidates = [2, 3, 6, 7], target = 7
Output: [[2,2,3],[7]]

Example 2

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

Constraints

  • 1 ≤ candidates.length ≤ 30
  • 2 ≤ candidate ≤ 40
  • 1 ≤ target ≤ 40

Pattern clues in the wording

  • → "All combinations" summing to a target
  • → Elements reusable

These clues point to Backtracking: Build a candidate one choice at a time; when a choice can't lead to an answer, undo it and try the next.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

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

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
candidates = [2,3,6,7]
target = 7
[[2,2,3],[7]]
2
candidates = [2,3,5]
target = 8
[[2,2,2,2],[2,3,3],[3,5]]
3
candidates = [2]
target = 1
[]

From slow to fast

Approaches

1. Backtracking with reuse and pruning · Exponential in target / min(candidate)
1

Backtracking with reuse and pruning

Time Exponential in target / min(candidate) Space O(target / min) depth

dfs(start, remaining): if remaining == 0 record. For i from start: if candidates[i] > remaining break (sorted); choose it and recurse with i (reuse allowed).

Approach 1
import java.util.*;

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

    private void dfs(int[] c, int start, int remaining, List<Integer> path, List<List<Integer>> out) {
        if (remaining == 0) { out.add(new ArrayList<>(path)); return; }
        for (int i = start; i < c.length; i++) {
            if (c[i] > remaining) break;          // sorted: every later one is bigger
            path.add(c[i]);
            dfs(c, i, remaining - c[i], path, out);
            path.remove(path.size() - 1);
        }
    }
}

Verdict: Pruning keeps it fast for the given limits.

Before you submit

Edge cases and common mistakes

Test these inputs

  • No combination (e.g. [2], target 1)
  • Target equals a candidate

Mistakes people make

  • Recursing with i + 1 (forbids reuse).
  • Recursing from 0 (produces the same combination in different orders).

Interview

Follow-up questions

What if you only need the number of combinations?