Find all unique combinations of k distinct numbers from 1 to 9 that add up to n.
Combination Sum III
Choose exactly k distinct numbers from the set {1, 2, 3, 4, 5, 6, 7, 8, 9} so that their sum is exactly n.
Return all valid combinations. Each number may be used at most once, and combinations should not contain duplicate sets of numbers.
You may return the answers in any order.
Input Format
- Two integers
kandn. kis the number of values to choose.nis the target sum.
Output Format
- Return a list of all distinct combinations.
- Each combination should contain exactly
knumbers in strictly increasing order.
Constraints
1 <= k <= 91 <= n <= 60- Numbers can only be chosen from
1to9 - Each number can be used at most once
Example 1
Input
k = 3, n = 7
Output
[[1,2,4]]
Explanation
The only 3-number combination from 1..9 that sums to 7 is [1,2,4].
Example 2
Input
k = 3, n = 9
Output
[[1,2,6],[1,3,5],[2,3,4]]
Explanation
These are the valid increasing combinations of three distinct numbers from 1..9 whose sum is 9.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.