Loading 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.
Example 1
Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation: The only way to pick 3 different digits from 1-9 that add up to 7 is 1 + 2 + 4.
Example 2
Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation: The three different digits that add up to 9 can be 1 + 2 + 6, 1 + 3 + 5 or 2 + 3 + 4. No other triple works.
Example 3
Input: k = 4, n = 1
Output: []
Explanation: The smallest sum of 4 different digits is 1 + 2 + 3 + 4 = 10, which is already more than 1, so no combination exists.
Build combinations by trying digits in increasing order, each used at most once. Carry a start index so digits never repeat and combinations aren't regenerated in different orders. Prune as soon as a digit exceeds the remaining sum.
Run checks all cases above. Submit evaluates all test cases.