Combination Sum III

Find every combination of k distinct numbers, chosen only from the digits 1 through 9, that adds up to exactly n.

Two rules govern which combinations are valid:

Only the numbers 1 to 9 may be used.
Each number is used at most once within a combination.

Return a list of all valid combinations. The list must not contain the same combination twice, and combinations may be returned in any order. Because each combination is a set of distinct digits, [1,2,4] and [4,2,1] are the same combination — list it once.

Hints

· Stuck? Reveal one nudge at a time.

You're choosing a fixed number of distinct digits from a tiny pool — how big is that pool really?

Once you've picked a digit, you never look back at it or any smaller one. What does that suggest about the order you should explore in?

Build the combination one digit at a time and abandon a branch the moment the remaining count or remaining sum can't work — classic backtracking with pruning.

Common doubts

No — each of 1–9 may be used at most once, so every combination is strictly increasing.

No. Order does not matter; a combination is a set. Always emitting digits in increasing order removes the duplicates for free.

Return an empty list. For example k = 4, n = 1 is impossible because the four smallest distinct digits already sum to 10.

Interview follow-ups

· What an interviewer asks next.

That's Combination Sum — drop the 'move past the current digit' rule and recurse from the same index so a value can repeat.

A dynamic-programming count over (digits used, running sum) avoids materializing every combination.

Fun facts

The entire search space is at most 2^9 = 512 subsets — this problem is really a lesson in pruning, not raw scale.
The same increasing-order backtracking skeleton powers Combinations, Subsets, and Combination Sum — learn it once, reuse it everywhere.

Asked at

AmazonGoogleMicrosoftAdobe

Frequently Sometimes Occasionally

Example 1

Input: k = 3, n = 7
Output: [[1,2,4]]
1 + 2 + 4 = 7, and there is no other way to pick 3 distinct digits summing to 7.

Example 2

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
1 + 2 + 6 = 9, 1 + 3 + 5 = 9, and 2 + 3 + 4 = 9 are the only valid combinations.

Example 3

Input: k = 4, n = 1
Output: []
The smallest sum of 4 distinct digits is 1 + 2 + 3 + 4 = 10 > 1, so no combination exists.

Constraints

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

Combination Sum III looks like a search over a huge space, but the pool of numbers is tiny — just the digits 1 to 9. The real skill here is pruning: refusing to explore branches that cannot possibly work. We'll build from an honest brute force to a clean backtracking solution.

Prerequisites

Before you start

· Concepts used directly in the solution.

Recursion. We build one combination digit by digit and undo each choice as the call returns.

Backtracking. Explore a choice, recurse, then take it back to try the next — the depth-first skeleton behind this solution.

Combinations. We want unordered groups of k numbers, so we always move forward and never revisit a smaller digit.

Understand the problem

In plain English: choose exactly k numbers from the fixed pool {1,2,…,9}, no repeats, whose total is n; report every such choice once.

Worked example — k = 3, n = 9

k = 3, n = 9  →  choose 3 distinct digits from 1..9 summing to 9

  1 + 2 + 6 = 9  ✓
  1 + 3 + 5 = 9  ✓
  2 + 3 + 4 = 9  ✓
  (1 + 2 + 5 = 8 ✗,  1 + 4 + 5 = 10 ✗, ...)

  answer: [[1,2,6],[1,3,5],[2,3,4]]

Clarifying questions

Asking these before writing code shows you understand the boundaries of the problem, not just the happy path.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Are numbers always drawn only from 1 to 9, each used at most once?”

Confirms the pool is the fixed set 1..9 — that is exactly what lets us cap the search and move strictly forward.

Output shape

“Should each combination be sorted, and does the order of combinations matter?”

Emitting each combination in increasing order and the overall list in any order lets us dedupe simply by never looking backward.

Edge cases

“What should I return when nothing sums to n?”

An empty list — for example k = 4, n = 1, where the four smallest distinct digits already sum to 10.

The ideal opening — say it like this

Before I code, a couple of quick clarifications.

Can I assume every number comes from 1 to 9 and each is used at most once per combination?

And if nothing sums to n, I'll return an empty list — is that the expected result?

Key observations

1Aha

Always move forward to kill duplicates

If we always pick digits in increasing order, then after choosing d we only ever consider d+1..9. That makes every combination strictly increasing, so [1,2,4] can be produced but [4,2,1] never is — duplicates vanish for free.

choose 1 → then only {2..9}
choose 2 → then only {3..9}
...never look back at a smaller digit

2Aha

Stop the loop the moment a digit overshoots

Since digits only grow, if the current digit d is already larger than the sum we still need, every larger digit is too. We can break out of the loop instead of testing the rest.

3Aha

Two counters decide everything

Carry how many digits are still needed (k_left) and how much sum is still needed (sum_left). A valid combination is exactly the moment both hit 0 at the same time.

Brute force vs optimal

	Brute force	Optimal
Idea	List every k-subset, keep those summing to n	Build forward, prune dead branches early
Time	O(k · C(9,k))	O(C(9,k)) with heavy pruning
Space	O(k)	O(k)

The full code for both lives in the Approaches selector below.

Summary

Key takeaway

This is the increasing-order backtracking template — choose a digit, recurse forward, undo — with a two-counter prune (k_left, sum_left) that stops hopeless branches before they start. The same skeleton powers Combinations, Subsets, and Combination Sum.

backtrack(start, k_left, sum_left):
    if k_left == 0:
        if sum_left == 0: record path
        return
    for d from start to 9:
        if d > sum_left: break          # prune: d and all larger overshoot
        choose d
        backtrack(d + 1, k_left - 1, sum_left - d)
        un-choose d