Topics › Recursion and Backtracking › Subsequences Pattern

Combination Sum III

Medium TUF ID 866 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given two integers k and n. Find every combination of exactly k distinct digits from 1 to 9 whose sum is n. Each digit may be used at most once per combination, and a combination is a set, so [1, 2, 4] and [4, 2, 1] are the same and must be reported once. Return the combinations in any order; return an empty list if none exists.

Compared with the other Combination Sum problems the candidate pool is tiny and fixed, which makes the whole search space small (there are only 2^9 = 512 subsets of the digits) and lets us compare three formulations of the same backtracking idea side by side.

Constraints: 2 ≤ k ≤ 9, 1 ≤ n ≤ 60.

Example 1

k = 3, n = 7
answer = [[1, 2, 4]]           // the only three distinct digits with sum 7

Example 2

k = 3, n = 9
answer = [[1, 2, 6], [1, 3, 5], [2, 3, 4]]

Example 3

k = 4, n = 1
answer = []                    // four distinct digits sum to at least 1 + 2 + 3 + 4 = 10

Approach 1: Brute force, every subset of the digits

Intuition. With only nine candidates, “try every subset” is genuinely affordable. A 9-bit mask names each subset: bit d - 1 set means digit d is in. Keep the masks with exactly k set bits (Integer.bitCount) whose digits add up to n. The method is a useful sanity check for the recursive versions and is the fastest thing to write; it just does not generalise to a larger candidate pool, where 2^n masks are far too many.

Algorithm.

1. For every mask from 0 to 511:
2. Skip it unless Integer.bitCount(mask) == k.
3. Collect the digits whose bit is set, summing as you go.
4. If the sum equals n, record the digit list.

static List<List<Integer>> bruteForce(int k, int n) {
    List<List<Integer>> out = new ArrayList<>();
    for (int mask = 0; mask < (1 << 9); mask++) {
        if (Integer.bitCount(mask) != k) continue;
        int sum = 0;
        List<Integer> combo = new ArrayList<>();
        for (int d = 1; d <= 9; d++) {
            if ((mask & (1 << (d - 1))) != 0) {
                sum += d;
                combo.add(d);
            }
        }
        if (sum == n) out.add(combo);
    }
    return out;
}

Complexity. Time O(2^9 · 9), a constant of about 4600 steps. Space O(k) per recorded combination, nothing else beyond the output.

Digits are collected in increasing order, so each subset appears exactly once and already sorted.

Approach 2: Pick / not-pick over the digits

Intuition. Treat the digits 1..9 as the input array of the subsequence pattern. At digit d, with k digits still to choose and n still to collect, either take d (go to d + 1 with k - 1 and n - d) or skip it (go to d + 1 with k and n). Success is k == 0 && n == 0. Two prunings make the tree small: if k == 0 we stop regardless of n (adding more digits can only increase the sum), and if n <= 0 while digits are still needed we stop, because every digit is at least 1 and the sum can only grow.

Algorithm.

1. pickRec(d, k, n, cur): if k == 0, record cur when n == 0; return.
2. If d > 9 or n <= 0, return.
3. Pick: append d, recurse with (d + 1, k - 1, n - d), remove it.
4. Skip: recurse with (d + 1, k, n).

static List<List<Integer>> pickNotPick(int k, int n) {
    List<List<Integer>> out = new ArrayList<>();
    pickRec(1, k, n, new ArrayList<>(), out);
    return out;
}

static void pickRec(int d, int k, int n, List<Integer> cur, List<List<Integer>> out) {
    if (k == 0) {
        if (n == 0) out.add(new ArrayList<>(cur));
        return;
    }
    if (d > 9 || n <= 0) return;                       // digits ran out, or the remaining sum cannot be reached
    cur.add(d);                                        // pick d
    pickRec(d + 1, k - 1, n - d, cur, out);
    cur.remove(cur.size() - 1);
    pickRec(d + 1, k, n, cur, out);                    // skip d
}

Complexity. Time O(2^9 · k): at most 512 leaves, each successful one copying k digits, and in practice far fewer thanks to the two prunings. Space O(9) for the recursion depth and the working list.

Approach 3: Optimal, loop with pruning on both count and sum

Intuition. The loop form chooses the next digit directly: at each level, iterate d from start to 9, append it, and recurse from d + 1. Because digits are increasing, two cheap tests end a level early. If d > n, this digit and every larger one overshoots the remaining sum. If fewer than k digits remain in d..9 (that is, 10 - d < k), we can never collect enough digits from here on. Together they keep the recursion from ever entering a level that cannot succeed. A third, optional test is the maximum reachable sum from the k largest remaining digits; it prunes a little more but is rarely needed at this size.

Algorithm.

1. loopRec(start, k, n, cur): if k == 0, record cur when n == 0; return.
2. For d = start .. 9: break if d > n; break if 10 - d < k.
3. Append d, recurse with (d + 1, k - 1, n - d), remove it.

static List<List<Integer>> optimal(int k, int n) {
    List<List<Integer>> out = new ArrayList<>();
    loopRec(1, k, n, new ArrayList<>(), out);
    return out;
}

static void loopRec(int start, int k, int n, List<Integer> cur, List<List<Integer>> out) {
    if (k == 0) {
        if (n == 0) out.add(new ArrayList<>(cur));
        return;
    }
    for (int d = start; d <= 9; d++) {
        if (d > n) break;                              // d, and every larger digit, overshoots the sum
        if (10 - d < k) break;                         // fewer than k digits remain in d..9
        cur.add(d);
        loopRec(d + 1, k - 1, n - d, cur, out);
        cur.remove(cur.size() - 1);
    }
}

Dry run on k = 3, n = 9:

Result: [1, 2, 6], [1, 3, 5], [2, 3, 4].

Complexity. Time O(C(9, k) · k): every leaf that is reached corresponds to a distinct k-subset of the digits (the pruning never lets a level start that cannot be completed), so the work is bounded by the number of k-subsets times the cost of copying one. The maximum of C(9, k) is C(9, 4) = 126. Space O(k) for the recursion and the working list.

Edge cases and pitfalls

• Impossible sums. k = 2, n = 18 has no answer because 8 + 9 = 17 is the largest pair; k = 9, n = 44 has none because the nine digits are forced and they sum to 45. All three methods return an empty list rather than a list containing an empty combination.
• Reusing a digit. Recursing from d instead of d + 1 would allow [3, 3, 3] for k = 3, n = 9. The digits must be distinct.
• Order duplicates. Looping from 1 at every level instead of from start would yield [1, 2, 6], [2, 1, 6], [6, 1, 2], and so on. Choosing digits in increasing order keeps each set unique.
• Stopping at k == 0 only. Checking n == 0 without k == 0 would record [9] for k = 3, n = 9. Both counts must be satisfied together.
• Copying the working list. Store new ArrayList<>(cur), not cur, which is mutated by later backtracking.
• Pruning direction. The 10 - d < k test must be a break, not a continue: once too few digits remain, every larger d leaves even fewer.

Related problems

• Combination Sum allows unlimited reuse of arbitrary candidates.
• Combination Sum II forbids reuse and handles duplicate candidates with a skip rule.
• Power Set generates every subset without a size or sum constraint.
• Count all subsequences with sum K counts the subsets that hit a target instead of listing them.
• Subsets I lists the sums of all subsets, the quantity this problem filters on.