组合Ⅲ 力扣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;
}
}
}