组合Ⅲ 力扣216

一、题目

        

二、思想

        依旧是回溯算法的运用，遵从回溯模板！

三、代码

class Solution {List<List<Integer>> result= new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();int sum = 0;public List<List<Integer>> combinationSum3(int k, int n) {backTracking(n,k,1);return result;}public void backTracking(int targetSum,int k,int startIndex){//剪枝if (sum > targetSum) {return;}//4.回溯函数终止条件if(path.size() == k ) {if (sum == targetSum) result.add(new ArrayList<>(path));//5.返回上一层，叶子节点的上一层return;}//6.剪枝for(int i = startIndex;i <= 9 - (k - path.size()) + 1;i++){//7.增加节点,统计总和sum += i;path.add(i);//8.往下搜backTracking(targetSum,k,i+1);//9.回溯撤销处理结果path.removeLast();sum -= i;}}
}