216. Combination Sum III - Detailed Explanation

Find all combinations of k distinct numbers from 1 to 9 that add up to n. Each digit may be used at most once, and each combination may appear only once in the output. The search space is tiny, so the interview is not about speed. It is about whether you can write a backtracking routine that enumerates each combination exactly once.

It appears in the backtracking section of LeetCode 75.

Examples

Constraints

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

Because the digits are fixed at 1 through 9, the smallest sum for k digits is 1 + 2 + ... + k and the largest is 9 + 8 + ... . Anything outside that window is immediately impossible, which is a cheap check worth mentioning.

Which pattern this problem belongs to

This is the backtracking pattern, generating combinations rather than permutations. Backtracking builds a partial answer, recurses, and then undoes the last choice before trying the next one. The undo step is what makes it backtracking rather than plain recursion.

The distinction between combinations and permutations is the crux here. [1,2,4] and [2,1,4] are the same combination, and the output must contain it once. The standard device is to force the digits to increase: each recursive call starts from a digit higher than the one just used. That makes every combination reachable by exactly one path through the tree, so duplicates become impossible by construction rather than by filtering afterwards.

Approach

Recurse carrying the current partial combination, the index to start from, and how much of the target remains. At each level, try each digit from the start index up to 9. Append it, recurse with a start of one higher and a reduced remainder, then pop it.

Two prunes do most of the work:

• Stop when the remainder goes negative. Digits are all positive, so once you overshoot, no deeper choice can recover.
• Stop when not enough digits remain. If you still need k - len(path) digits and fewer than that are left between the current digit and 9, the branch cannot complete.

With both, the recursion explores only a small part of the tree. The theoretical bound is the number of ways to choose k digits from 9, which is at most 126 combinations, so this is fast under any implementation. The prunes are still worth writing because the interviewer is checking whether you see them.

Record a copy of the path when the remainder reaches zero and the path holds exactly k digits. Appending the list itself rather than a copy is the classic bug, because later mutation then corrupts every stored answer.

Python code

def combination_sum3(k, n):
    """Backtracking over increasing digits. Each combination is reached once."""
    results = []
    path = []

    def backtrack(start, remaining):
        if len(path) == k:
            if remaining == 0:
                results.append(path[:])   # copy, not the live list
            return
        for digit in range(start, 10):
            if digit > remaining:         # prune: overshoot
                break
            if 9 - digit + 1 < k - len(path):   # prune: too few digits left
                break
            path.append(digit)
            backtrack(digit + 1, remaining - digit)
            path.pop()

    backtrack(1, n)
    return results

Java code

public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> results = new ArrayList<>();
    backtrack(1, n, k, new ArrayList<>(), results);
    return results;
}

private void backtrack(int start, int remaining, int k,
                       List<Integer> path, List<List<Integer>> results) {
    if (path.size() == k) {
        if (remaining == 0) results.add(new ArrayList<>(path));
        return;
    }
    for (int digit = start; digit <= 9; digit++) {
        if (digit > remaining) break;
        if (10 - digit < k - path.size()) break;
        path.add(digit);
        backtrack(digit + 1, remaining - digit, k, path, results);
        path.remove(path.size() - 1);
    }
}

Complexity

Common mistakes

• Storing the path instead of a copy. The path is mutated after it is recorded, so every stored result ends up identical or empty. Copy it at the moment you record it.
• Starting each recursive call from 1. That generates permutations and duplicates. The next call must start at digit + 1.
• Forgetting the pop. Without undoing the choice, the path grows without bound and the answers are wrong.
• Checking only the sum. A combination must hold exactly k digits and sum to n. Both conditions are required before recording.

Related problems

• Letter Combinations of a Phone Number, which is the same recursion shape over a different choice set.
• Combination Sum, which allows reuse of a number and so recurses with the same start index.
• Subsets, which records at every node rather than only at depth k.

How to Prepare

• Write the three lines in order every time: choose, recurse, undo. That skeleton is the whole pattern, and it transfers to permutations, subsets and word search.
• State why duplicates cannot occur. The increasing-start device is the answer, and being able to explain it is what the question tests.
• Learn the family together. Grokking the Coding Interview teaches backtracking as one chapter covering subsets, permutations and combinations, with the summary in the most common LeetCode patterns.