找出所有相加之和为 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

问题简要描述：返回所有的有效组合的列表

细节阐述:

1.  dfs(i,s)，表示当前枚举到数字 i，还剩下和为 s 的数字需要枚举

Java

class Solution {List<List<Integer>> ans = new ArrayList<>();List<Integer> t = new ArrayList<>();int k;    public List<List<Integer>> combinationSum3(int k, int n) {this.k = k;dfs(1, n);return ans;}void dfs(int i, int s) {if (s == 0) {if (t.size() == k) {ans.add(new ArrayList<>(t));}return;}if (i > 9 || i > s || t.size() >= k) {return;}t.add(i);dfs(i + 1, s - i);t.remove(t.size() - 1);dfs(i + 1, s);}
}

 Python3

class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:def dfs(i: int, s: int):if s == 0:if len(t) == k:ans.append(t[:])returnif i > 9 or i > s or len(t) >= k:returnt.append(i)dfs(i + 1, s - i)t.pop()dfs(i + 1, s)t = []ans = []dfs(1, n)return ans        

TypeScript

function combinationSum3(k: number, n: number): number[][] {let ans: number[][] = [];let t: number[] = [];const dfs = (i: number, s: number) => {if (s == 0) {if (t.length == k) {ans.push(t.slice());}return;}if (i > 9 || i > s || t.length >= k) {return;}t.push(i);dfs(i + 1, s - i);t.pop();dfs(i + 1, s);}dfs(1, n);return ans;    
};