Combination Sum III — Medium Problem & Solution

Problem statement

Find every way to choose exactly k different digits from 1 to 9 whose sum is exactly n. Each digit may be used at most once in a combination.

Write each combination in increasing order and list the combinations in lexicographic order. Return an empty list if no combination works.

Example 1

Input: k = 3, n = 7
Output: [[1,2,4]]

Example 2

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]

Example 3

Input: k = 4, n = 1
Output: []
Explanation: Four different digits add up to at least 1 + 2 + 3 + 4 = 10.

Constraints

• 2 <= k <= 9
• 1 <= n <= 60

How to solve Combination Sum III

Choose digits in strictly increasing order with a depth-first search. Each combination is generated once, already sorted, and the branches come out in lexicographic order.

Approach

1. dfs(next, remaining, path): if path has k digits, record it when remaining == 0 and return.
2. Otherwise try each digit d from next to 9; stop when d > remaining (larger digits only overshoot).
3. Push d, recurse with d + 1 and remaining - d, pop.
4. Start with dfs(1, n, []).

Why it works

Strictly increasing choices make every set of digits correspond to exactly one path, and trying smaller digits first at every depth lists the sets in lexicographic order (all have the same length k).

Complexity

• Time — O(C(9, k) · k)
• Space — O(k)

Pitfalls

• Digits must be distinct and between 1 and 9 — 0 is not allowed.
• Large n (above 45) has no answer at all; the search handles it, but do not assume a result exists.
• Record only when both the count and the sum match.

Reference solution

Python

from typing import List

def combinationSum3(k: int, n: int) -> List[List[int]]:
    out = []
    path = []

    def dfs(nxt, rem):
        if len(path) == k:
            if rem == 0:
                out.append(path[:])
            return
        for d in range(nxt, 10):
            if d > rem:
                break
            path.append(d)
            dfs(d + 1, rem - d)
            path.pop()

    dfs(1, n)
    return out

JavaScript

var combinationSum3 = function(k, n) {
    var out = [];
    var path = [];
    var dfs = function(nxt, rem) {
        if (path.length === k) {
            if (rem === 0) out.push(path.slice());
            return;
        }
        for (var d = nxt; d <= 9; d++) {
            if (d > rem) break;
            path.push(d);
            dfs(d + 1, rem - d);
            path.pop();
        }
    };
    dfs(1, n);
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Non-decreasing Subsequences Medium
• Construct the Lexicographically Largest Valid Sequence Medium
• Matchsticks to Square Medium
• Combination Sum II Medium
• Permutations II Medium
• Subsets II Medium