Description
Find all valid combinations of k numbers that sum up to n, using only digits 1 through 9. Each number may be used at most once.
Examples
Input:
k = 3, n = 7Output:
[[1,2,4]]Explanation:
Only [1,2,4] sums to 7.
Input:
k = 2, n = 9Output:
[[1,8],[2,7],[3,6],[4,5]]Explanation:
Need exactly 2 numbers that sum to 9. All valid pairs using digits 1-9 are: [1,8], [2,7], [3,6], and [4,5]. Each pair uses distinct digits and sums to 9.
Input:
k = 4, n = 10Output:
[[1,2,3,4]]Explanation:
Need exactly 4 numbers that sum to 10. The only combination possible is [1,2,3,4] since it uses the smallest 4 digits (1+2+3+4=10). Any other combination of 4 distinct digits from 1-9 would sum to more than 10.
Constraints
- •
2 ≤ k ≤ 9