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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Combination Sum III and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →