题意理解：

        求数字1-9，任取k个数，其和为n的组合

        每个数字只能用一遍

        这里的求的是组合，即k个值不看顺序。

解题思路：按照回溯法解题模板

        1.确定返回值及参数

                List<>results :记录符合条件的结果

                path：用来记录k个数的组合

                //sum当前path里的值的和

                //startIndex指示之前没用过的数值作为新起点

                void backtracking(n,k,sum,startIndex)

        2.确定终止条件

                当且仅当sum==n时，找到结果，result.add(path) return;

                //此时可以又一个剪枝操作，sum>n时，即可剪枝。 return;

        3.单层逻辑

        for(int i=startIndex;i<=9;i++){//这里也可以进行剪枝，当当前startIndex指向的位置不足以取k个数时，剪枝。

                i<9-（k-path.size()）+1

                path.push(i);

                sum+=i;

                backtracking(n,k,sum,i+1);

                //回溯：

                sum-=i

                path.pop();

        }

1.暴力回溯+三个位置的剪枝

剪枝1：剪掉sum>n的

剪枝2：剪掉path.size组合数>k的

剪枝3：剪掉不足以凑出k个数组合的

List<List<Integer>> results=new ArrayList<>();LinkedList<Integer> path=new LinkedList<>();public List<List<Integer>> combinationSum3(int k, int n) {backtracking(k,n,0,1);return results;}public void backtracking(int k,int n,int sum,int startIndex){//终止条件//剪枝1:剪枝值超过n的if(sum>n) return;//剪枝2：超过k个数的组合else if (path.size()>k) return;else if (sum==n&&path.size()==k) {results.add(new ArrayList<>(path));return;}//单层逻辑:剪枝3：不能保证k个数for(int i=startIndex;i<=9-(k-path.size())+1;i++){path.add(i);sum+=i;backtracking(k,n,sum,i+1);path.removeLast();sum-=i;}}

2.代码可优化的地方

//单层逻辑:剪枝1：不能保证k个数for(int i=startIndex;i<=9-(k-path.size())+1;i++){path.add(i);sum+=i;backtracking(k,n,sum,i+1);path.removeLast();sum-=i;}----------------------------------------------------------------
优化：
//单层逻辑:剪枝3：不能保证k个数for(int i=startIndex;i<=9-(k-path.size())+1;i++){path.add(i);backtracking(k,n,sum+i,i+1);path.removeLast();}

3.分析

时间复杂度：O(m×2^m)

空间复杂度：O(m)

m为集合大小