616. K Digits to N
A lock has k dials, and every dial must show a different digit from 1 to 9. The lock opens when the shown digits add up to exactly n. Since the dials are interchangeable, two settings that use the same set of digits are considered the same.
Return every set of k different digits from 1 to 9 whose sum is n. Each set must appear once. The sets may be returned in any order and the digits inside a set may be in any order. Return an empty array when no such set exists.
Example 1
- Input:
- k = 3, n = 9
- Output:
- [[1,2,6],[1,3,5],[2,3,4]]
- Explanation:
Three different digits summing to 9:
[1, 2, 6],[1, 3, 5]and[2, 3, 4].
Example 2
- Input:
- k = 2, n = 20
- Output:
- []
- Explanation:
The two largest digits are 8 and 9, which sum to only 17, so nothing works.
Example 3
- Input:
- k = 4, n = 10
- Output:
- [[1,2,3,4]]
- Explanation:
The only set of four different digits with sum 10 is
[1, 2, 3, 4].
Constraints
- 1 ≤
k≤ 9 - 1 ≤
n≤ 60
How this problem is judged
- Answers
- Lists at every level may be in any order. Duplicates still count.
Expected complexity
- Time
- O(C(9, k) * k)
- Space
- O(k)