196. Combination Sum III
Given two integers k and n, find every way to pick exactly k different numbers from 1 through 9 whose sum is exactly n. Each digit 1–9 may appear at most once inside a combination, and two combinations that contain the same numbers count as the same combination.
Return all valid combinations as a list of lists: write each combination with its numbers in increasing order, and list the combinations in lexicographic order (so [1, 2, 6] comes before [1, 3, 5]). If no combination works, return an empty list.
The pool is tiny — nine candidates — so the interesting part is generating the combinations cleanly and pruning dead branches early.
Example 1:
Input: k = 3, n = 8
Output: [[1, 2, 5], [1, 3, 4]]
Explanation: The only ways to write 8 as a sum of three distinct digits are 1 + 2 + 5 and 1 + 3 + 4. Each is printed in increasing order, and [1, 2, 5] precedes [1, 3, 4] lexicographically.
Example 2:
Input: k = 2, n = 13
Output: [[4, 9], [5, 8], [6, 7]]
Explanation: Three pairs of distinct digits reach 13: {4, 9}, {5, 8}, and {6, 7}.
Constraints:
- 1 ≤ k ≤ 9
- 1 ≤ n ≤ 60
- Only the numbers 1 through 9 may be used, each at most once per combination.
Hints:
There are only 2^9 = 512 subsets of {1, …, 9}. Even the bluntest enumeration — test every subset for the right size and sum — is instant.
For the backtracking shape: build combinations in increasing order by only ever appending digits larger than the last one chosen. That single rule kills duplicates and produces lexicographic order for free.
Prune hard: stop a branch when the running sum exceeds n, when fewer digits remain than you still need, or when even the largest remaining digits cannot reach n.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: k = 3, n = 8
Expected output: [[1, 2, 5], [1, 3, 4]]