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

 

本题k相当于了树的深度，9（因为整个集合就是9个数）就是树的宽度。

例如 k = 2，n = 4的话，就是在集合[1,2,3,4,5,6,7,8,9]中求 k（个数） = 2, n（和） = 4的组合。

选取过程如图：

图中，可以看出，只有最后取到集合（1，3）和为4 符合条件。

 

回溯三部曲

• 确定递归函数参数
• 确定终止条件
• 单层搜索过程

别忘了处理过程 和 回溯过程是一一对应的，处理有加，回溯就要有减！

class Solution {

    private List<List<Integer>> res=new ArrayList<>();;
    private LinkedList<Integer> path=new LinkedList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        process(n,0,1,k);
        return res;

    }

    private void process(int targetSum,int curSum,int startIndex,int k){
        //base case
        if(path.size()==k){
            if(targetSum==curSum){
                res.add(new ArrayList<>(path));
            }
        }
        if(curSum>targetSum){
            return;
        }
        for(int i=startIndex;i<=9-(k-path.size())+1;i++){
            curSum+=i;
            path.add(i);
            process(targetSum,curSum,i+1,k);
            // 回溯
            path.removeLast();
            // 回溯
            curSum-=i;
        }

    }
}