mediumBacktrackingPure DSA~20 min
Combinations of K Distinct Digits Summing to N
A voucher code uses exactly k distinct single digits (1-9) that add up to a fixed checksum. Enumerate every valid set of digits.
Problem
Find all valid combinations of k distinct numbers chosen from 1 to 9 that sum to n. Each number may be used at most once, and combinations must be unique (order does not matter). Return the list of combinations.
Input
Two integers k (count of numbers) and n (target sum).
Output
A list of combinations, each a list of k distinct digits in increasing order.
Constraints
- 2 <= k <= 9
- 1 <= n <= 60
Examples
Example 1
Input
k = 3, n = 7
Output
[[1,2,4]]
Only 1+2+4 = 7 uses three distinct digits.
Example 2
Input
k = 3, n = 9
Output
[[1,2,6],[1,3,5],[2,3,4]]
Three valid combinations.