183. Combination Sum III

Medium · Backtracking

Find every combination of exactly k distinct numbers, each between 1 and 9, that add up to a target n. Each number may be used at most once within a combination.

The input is [k, n]. Return a list of combinations. Each combination must be sorted in ascending order, and the list of combinations must be sorted lexicographically.

Examples

Example 1
Input: [3,7]
Output: [[1,2,4]]
Explanation: 1 + 2 + 4 = 7 is the only set of three distinct digits.
Example 2
Input: [3,9]
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation: Three triples of distinct digits sum to 9.

Constraints