Skip to main content

216. Combination Sum III

medium

Find every combination of exactly k distinct numbers from 1-9 that sum to n. Tiny search space, but a great mini-problem for stacking three backtracking constraints — distinct, fixed k, exact sum.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Find all valid combinations of k numbers that sum up to n such that the following conditions are true: Only numbers 1 through 9 are used. Each number is used at most once. Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Constraints

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

Examples

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
[]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Recurse with (start, remaining, path) where start ranges over 1..9.

Hint 2

Base case: path.length == k AND remaining == 0 -> snapshot.

Hint 3

Two prunes: (a) if path.length > k, return; (b) if start > 9 or remaining < 0, return.

Hint 4

Loop i from start to 9; skip if i > remaining.

Solution approach

Reveal approach

Backtrack with (start, remaining, path). Base case: path.length == k -> if remaining == 0, snapshot to result; return either way. Recursive case: for i from start to 9, if i > remaining break, push i, recurse(i + 1, remaining - i, path), pop. The 'i + 1' enforces strict-increasing order so each combination appears once. The 'i > remaining' break is a meaningful prune because the search space is small (1..9) and the target tight. Time is bounded by C(9, k) since we only generate strictly-increasing length-k sequences; space is O(k) recursion stack.

Complexity

Time
O(C(9, k) * k)
Space
O(k)

Related patterns

  • backtracking
  • recursion

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple

More Recursion practice problems

See all Recursion problems →