组合总和III

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

• 所有数字都是正整数。
• 解集不能包含重复的组合。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

需要注意的是，不能包含重复的数字，不能包含重复的组合。

class Solution {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(n, k, 1, new ArrayDeque<Integer>());
        return ans;
    }
/**
* @param n 剩余的数字之和
* @param k 剩余的数字个数
* @param min 当前能选取的最小数字
* @param path 递归路径
*/
    public void dfs(int n, int k, int min, Deque<Integer> path){
        // 和为 0 且 剩余数字个数为 0 将当前路径加入结果
        if(n == 0 && k == 0){
            ans.add(new ArrayList<Integer>(path));
            return;
        }
		//从最小值开始递归
        for(int i = min; k > 0 && i <= 9; i++){
            //剪枝
            if(i > n){
                break;
            }
            path.addLast(i);
            //下一次选择只能选择比自己大的数字
            dfs(n - i, k - 1, i + 1, path);
            path.removeLast();
        }
    }
}