力扣算法：组合总和III

原题：https://leetcode-cn.com/problems/combination-sum-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]]

解题思路：

 这与昨天的两道题很相似，所以直接使用回溯的方式。明确条件即可

public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> daan =new ArrayList<>();
        backtrack(result,k,n,daan,1);
        return result;
    }

    public void backtrack(List<List<Integer>> result,int k,int n,List<Integer> daan,int start){
        if(n<0){
            return;
        }
        if(k==0){
            if(n==0){
                result.add(new ArrayList<Integer>(daan));
                return;
            }
            return;
        }

        for(int i=start;i<=9;i++){
            if(n-i>=0){
                daan.add(i);
                backtrack(result,k-1,n-i,daan,i+1);   //这个最后一个参数用 start+1 不可，会出现重复数字的情况。
                daan.remove(daan.size()-1);
            }
        }