Return all k-digit combinations from 1 through 9 whose sum is n, in canonical DFS order. Test your code and explore the solution. Free online practice.

Combination Sum III – Solve Online

Sort List

Path Sum III

Return all k-digit combinations from 1 through 9 whose sum is n, in canonical DFS order.

Given two integers `k` and `n`, return every valid combination of exactly `k` distinct digits chosen from `1` through `9` whose sum is `n`. Each digit may be used at most once in a combination.

For this question, keep the output deterministic: each combination **must** list its digits in increasing order, and the outer list **must** follow the natural depth-first search order created by trying candidate digits `1` through `9` in increasing order at every backtracking step. When a partial combination reaches length `k` and sum `n`, record it immediately; that DFS discovery order is the required output order.

**Input / output**
- Input: `k: int`, `n: int`
- Output: `int[][]` in canonical DFS order

## Example
```json
Input: {"k":3,"n":9}
Output: [[1,2,6],[1,3,5],[2,3,4]]
```

## More examples
1. `k = 3, n = 7` returns `[[1,2,4]]`.
2. `k = 4, n = 1` returns `[]` because even the smallest 4 distinct digits sum to `10`.
3. `k = 9, n = 45` returns `[[1,2,3,4,5,6,7,8,9]]`.

## Constraints
- `1 <= k <= 9`
- `1 <= n <= 60`
- Use only digits `1..9`
- Every combination must contain exactly `k` distinct digits

## Follow-up
How can you prune the backtracking tree early by proving that the remaining slots are too small or too large to ever reach the target sum?

- You are choosing exactly `k` distinct digits from the fixed set `1..9`, so this is a small combinatorial backtracking problem.
- Distinctness and increasing order come naturally if each recursive call only considers later digits than the one just chosen.
- Because each level tries digits in ascending order, the DFS itself produces the required canonical output order without any post-sorting.

Recognize the search space

- Keep a `path` for the current combination, a `start` digit for the next choice, and the running sum so far.
- If the path already has `k` digits, record it only when the sum is exactly `n`.
- Otherwise, try every next digit from `start` through `9`, recurse with `digit + 1`, then undo the choice.
- This baseline already guarantees no repeated digits, increasing order inside each combination, and canonical DFS order across the answer list.

Plain backtracking with increasing digits

- The baseline works because the search space is tiny, but you can cut many branches before recursing.
- If you still need `remaining_count` digits, the smallest possible extra sum comes from taking the next `remaining_count` consecutive digits starting at `start`.
- The largest possible extra sum comes from taking the biggest `remaining_count` digits ending at `9`.
- If `remaining_sum` falls outside that `[min_possible, max_possible]` range, this branch can never succeed and should stop immediately.

Prune impossible branches earlier

Backtracking still explores combinations in the exact same canonical order, but arithmetic bounds prune branches whose remaining slots cannot possibly add up to the target. The search uses `O(k)` extra recursion/path space, and the total work is `O(C(9, k) * k)` in the worst case because every valid or explored combination prefix has length at most `k`.