找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
示例 3:
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
提示:
2 <= k <= 9
1 <= n <= 60
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/combination-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
找到所有之类的题，一般都可以用回溯。
为了保证不重复，可以让所有答案都从小到大排列。
class Solution { private final boolean[] NUMS = new boolean[10]; public List<List<Integer>> combinationSum3 (int k, int n) { List<List<Integer>> res = new ArrayList<>(); dfs(res, new ArrayList<>(), k, n, 0, 0, 1); return res; } // res 存储答案，list 作为路径，count 计数，看是否已经达到 k 个。sum 是当前路径的和。index 是开始的下标，可以找的答案都是从 小到大排列。 private void dfs (List<List<Integer>> res, List<Integer> list, int k, int n, int count, int sum, int index) { if (count == k) { if (sum == n) { res.add(new ArrayList<>(list)); } return; } for (int i = index; i < 10; i++) { if (!NUMS[i]) { if (sum + i > n) { return; } NUMS[i] = true; list.add(i); dfs(res, list, k, n, count + 1, sum + i, i + 1); list.remove(list.size() - 1); NUMS[i] = false; } } } }
