AlgoViz
HomeRecursion

Combination Sum III

Medium

k numbers from 1..9, each once

Problem

Find all combinations of k distinct numbers from 1..9 that sum to n (each number used once).

In simple words

Choose distinct digits 1-9, recursing on the remaining count and sum, and backtrack.

The idea

Recurse over the digits 1 to 9 choosing each at most once and moving forward only, tracking both the remaining target and how many numbers are still needed. Two counters mean two pruning opportunities.

The trick

  • Prune when the target goes negative or the count exceeds k.
  • Success requires both target == 0 and exactly k numbers chosen.
  • The forward-only walk keeps combinations sorted and unique.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

3
7
0
1

Step 1 of 2. Here's the example — k=3, n=7 Values: 3, 7.

1/2
Optimal
timeO(C(9,k))spaceO(k)
1f(start, k, target, cur):2  if k==0 and target==0: output; return3  for d from start to 9:4    if d>target: break5    cur.push(d); f(d+1, k-1, target-d, cur); cur.pop()

Input

array
[3, 7]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
k = 3, n = 7
Output:
[[1, 2, 4]]
Explanation:
Pick 3 distinct digits 1-9 summing to 7.

Example 2

Input:
k = 3, n = 9
Output:
[[1, 2, 6], [1, 3, 5], [2, 3, 4]]
Explanation:
Three ways to make 9.

Example 3

Input:
k = 2, n = 1
Output:
[]
Explanation:
Can't make 1 from two distinct digits → none.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.