Topics › Recursion and Backtracking › Subsequences Pattern

Combination Sum

Medium TUF ID 864 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array candidates of distinct positive integers and a positive integer target. Return every unique combination of candidates whose values add up to target. The same candidate may be used any number of times. Two combinations are the same if they use each value the same number of times, regardless of order, so [2, 2, 3] and [3, 2, 2] count once. The combinations may be returned in any order.

Constraints: 1 ≤ n ≤ 30, 2 ≤ candidates[i] ≤ 40, 1 ≤ target ≤ 40. The number of combinations is guaranteed to be below 150.

Example 1

candidates = [2, 3, 6, 7], target = 7
answer = [[2, 2, 3], [7]]      // 2 + 2 + 3 = 7 uses 2 twice; 7 alone also works

Example 2

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

Example 3

candidates = [2], target = 1
answer = []                    // nothing fits under 1

Approach 1: Brute force, choose a count for each candidate

Intuition. Because order does not matter, a combination is fully described by how many copies of each candidate it uses. Candidate c[i] can appear at most target / c[i] times, so we can walk through the candidates, try every copy count for each one, and check the total when every candidate has been decided. The method explores a huge number of count vectors whose sum is nowhere near target, and it only discovers that at the leaves, which is what makes it slow; but it is the clearest statement of what a “combination” is.

Algorithm.

bruteRec(i, cur): if i == n, sum cur; record a copy if the sum equals target.
Otherwise, for copies = 0 .. target / c[i]: recurse to i + 1 with the current cur, then append one more c[i] for the next round.
After the loop remove the target / c[i] + 1 copies that were appended, restoring cur.

static List<List<Integer>> bruteForce(int[] candidates, int target) {
    List<List<Integer>> out = new ArrayList<>();
    bruteRec(candidates, 0, target, new ArrayList<>(), out);
    return out;
}

static void bruteRec(int[] c, int i, int target, List<Integer> cur, List<List<Integer>> out) {
    if (i == c.length) {
        int sum = 0;
        for (int x : cur) sum += x;
        if (sum == target) out.add(new ArrayList<>(cur));
        return;
    }
    int maxCopies = target / c[i];                // more copies than this can never fit under target
    for (int copies = 0; copies <= maxCopies; copies++) {
        bruteRec(c, i + 1, target, cur, out);
        cur.add(c[i]);                            // one more copy of c[i] for the next round
    }
    for (int copies = 0; copies <= maxCopies; copies++) cur.remove(cur.size() - 1);
}

Complexity. Time O(Π (target / c[i] + 1) · n): the product over all candidates of the number of copy counts, times the O(n) summation at each leaf (the combination length is at most target / min(c)). For small candidates and a large target the product is enormous. Space O(target / min(c)) for the current combination plus the recursion depth O(n).

Every combination is generated exactly once because the count vector determines it, so no de-duplication is needed. The cleanup loop removes maxCopies + 1 elements because the body appended one copy after each of its maxCopies + 1 iterations.

Approach 2: Pick / not-pick with reuse

Intuition. The standard subsequence recursion decides, for each index, whether to take it and then moves on. To allow unlimited reuse, change exactly one thing: after picking c[i], stay at index i instead of advancing, so the same candidate can be picked again. After not picking, advance to i + 1, which is the moment we commit to never using c[i] again. Because every combination corresponds to one sequence of “pick, pick, …, not pick” decisions per index, each combination appears exactly once and never in a different order.

Pruning comes for free: the target is reduced as we pick, and since all candidates are positive we only pick when c[i] <= target. The recursion terminates because every pick strictly reduces the target and every not-pick advances the index.

Algorithm.

pickRec(i, target, cur): if i == n, record cur when target == 0 and return.
If c[i] <= target: append c[i], recurse with (i, target - c[i]), remove it again.
Recurse with (i + 1, target): leave c[i] out for good.

static List<List<Integer>> pickNotPick(int[] candidates, int target) {
    List<List<Integer>> out = new ArrayList<>();
    pickRec(candidates, 0, target, new ArrayList<>(), out);
    return out;
}

static void pickRec(int[] c, int i, int target, List<Integer> cur, List<List<Integer>> out) {
    if (i == c.length) {
        if (target == 0) out.add(new ArrayList<>(cur));
        return;
    }
    if (c[i] <= target) {                          // pick c[i] and stay at i: the same value may be reused
        cur.add(c[i]);
        pickRec(c, i, target - c[i], cur, out);
        cur.remove(cur.size() - 1);
    }
    pickRec(c, i + 1, target, cur, out);           // leave c[i] out for good
}

Complexity. Time O(2^t · k) where t = target / min(c) bounds the depth of the pick chain and k is the average combination length copied at a leaf; this is the usual loose bound and the real tree is far smaller because the target prunes most branches. Space O(t) for cur and for the recursion stack.

Approach 3: Optimal, sorted loop with early break

Intuition. Pick / not-pick walks to the end of the array even when the remaining target is already 0, and it keeps testing candidates that are far too large. Two refinements fix that. First, make target == 0 the success condition and return immediately: the moment the sum is reached there is nothing more to decide. Second, sort the candidates and, at each level, loop over the candidates from start onward; the first candidate larger than the remaining target lets us break, because every later candidate is larger still.

The loop form is the “for-loop recursion” of the subsequence pattern: each level chooses the next element to append, and passing j (not j + 1) as the next start allows the same value to be chosen again while forbidding earlier values, which is exactly what keeps combinations unique.

Algorithm.

Sort a copy of the candidates.
loopRec(start, target, cur): if target == 0, record cur and return.
For j = start .. n - 1: if c[j] > target, break.
Append c[j], recurse with (j, target - c[j]), remove it.

static List<List<Integer>> optimal(int[] candidates, int target) {
    int[] c = candidates.clone();
    Arrays.sort(c);
    List<List<Integer>> out = new ArrayList<>();
    loopRec(c, 0, target, new ArrayList<>(), out);
    return out;
}

static void loopRec(int[] c, int start, int target, List<Integer> cur, List<List<Integer>> out) {
    if (target == 0) {
        out.add(new ArrayList<>(cur));
        return;
    }
    for (int j = start; j < c.length; j++) {
        if (c[j] > target) break;                  // sorted: every later candidate is too big as well
        cur.add(c[j]);
        loopRec(c, j, target - c[j], cur, out);    // j, not j + 1: the same value may be reused
        cur.remove(cur.size() - 1);
    }
}

Dry run on candidates = [2, 3, 6, 7], target = 7:

target	cur	action
7	[]	j = 0: take 2
5	[2]	j = 0: take 2
3	[2, 2]	j = 0: take 2
1	[2, 2, 2]	j = 0: 2 > 1, break; back up
3	[2, 2]	j = 1: take 3 → target 0, record [2, 2, 3]; j = 2: 6 > 3, break
5	[2]	j = 1: take 3 → (1, 2, [2, 3]): 3 > 2, break; j = 2: 6 > 5, break
7	[]	j = 1: take 3 → (1, 4, [3]): take 3 → (1, 1): 3 > 1 break; 6 > 4 break
7	[]	j = 2: take 6 → (2, 1, [6]): 6 > 1, break
7	[]	j = 3: take 7 → target 0, record [7]

Complexity. Time O(2^t · k) as a loose upper bound with t = target / min(c), but the sort plus the break means no call is ever wasted on an oversized candidate, and the target == 0 exit stops each successful path at its first possible moment. Sorting costs O(n log n), negligible next to the search. Space O(t) for the stack and the current combination; the output itself is not counted.

Every combination is non-decreasing because start never moves backwards, and two different combinations differ in some position, so each appears exactly once.

Edge cases and pitfalls

Forgetting to allow reuse. Passing i + 1 after a pick (or j + 1 in the loop) turns the problem into Combination Sum II and loses [2, 2, 3].
Duplicates from unordered choice. Looping from 0 instead of start produces [2, 3, 2] as well as [2, 2, 3]. Always choose candidates in index order.
Copying the list. out.add(cur) stores a reference to the shared working list, which is emptied by later backtracking. Store new ArrayList<>(cur).
Unsorted input. Only Approach 3 needs sorting, and it sorts a clone so the caller’s array is untouched. The tests feed [7, 3, 2] and expect the same combinations as [2, 3, 7].
No answer. [2, 4] with target 7 returns an empty list, not a list containing an empty list. The success check is reached only when the target hits exactly 0.
Infinite recursion. The pick branch must strictly decrease the target, which is why candidates are positive; a zero candidate would recurse forever at the same index. Guard against it if the input is not trusted.

Combination Sum II forbids reuse and has duplicate candidates, which forces a skip-duplicates rule.
Combination Sum III fixes the candidates to 1..9 and the combination size to k.
Power Set is the plain pick / not-pick enumeration without a target.
Count all subsequences with sum K counts instead of listing, without reuse.
Subsets II uses the same sorted-loop skeleton to enumerate unique subsets.

Combination Sum

Problem

Approach 1: Brute force, choose a count for each candidate

Approach 2: Pick / not-pick with reuse

Approach 3: Optimal, sorted loop with early break

Edge cases and pitfalls

Related problems