思路分析
- 路径：当前已选的数字列表（比如 [1,2]）；
- 选择列表：当前可选择的数字（为了去重，只选比上一个数字大的数，比如选了 1 之后只选 2-9，避免重复组合）；
- 终止条件：
- 路径长度 == k：若路径和 == n，加入结果集；否则直接返回；
- 路径和 > n：提前剪枝（无需继续选数）；
- 剩余可选数字不足：比如已选 2 个数，还需选 3 个，但只剩 2 个数字可选，直接剪枝。
- 回溯逻辑：遍历选择列表，选一个数加入路径 → 递归 → 撤销选择（回溯）。
代码实现
// 保存最终结果List<List<Integer>>res=newArrayList<>();// 保存当前路径List<Integer>curPath=newArrayList<>();publicList<List<Integer>>combinationSum3(intk,intn){// 如果k大于n，直接返回空列表if(k>n){returnres;}// 回溯backtrack(1,0,k,n);returnres;}publicvoidbacktrack(intstart,intcurSum,intk,inttargetSum){// 如果当前和等于目标值，且长度为k，加入结果if(curSum==targetSum&&curPath.size()==k){res.add(newArrayList<>(curPath));return;}// 剪枝1：如果当前和大于目标值，直接返回if(curSum>targetSum){return;}// 剪枝2：如果当前路径长度加上可选的最大数还小于k，直接返回intremainCount=k-curPath.size();intremainNum=9-start+1;if(remainCount>remainNum){return;}// 开始遍历for(inti=start;i<=9;i++){// 选择curPath.add(i);curSum+=i;backtrack(i+1,curSum,k,targetSum);// 回溯curSum-=i;curPath.remove(curPath.size()-1);}}
代码关键部分解释
- 去重核心：start 参数控制每次选择的起始数字（比如选了 1 之后，下一轮只能选 2-9），避免出现 [1,2] 和 [2,1] 这样的重复组合。
- 剪枝优化（关键，提升效率）：
- 剪枝 1：当前路径和 > n，直接返回（比如选了 1+3=4，n=5 但还需选 1 个数，若下一个数选 2，和为 6>5，无需遍历）；
- 剪枝 2：剩余可选数字数量 < 还需选的数，直接返回（比如需要选 3 个数，当前从 8 开始选，只剩 8、9 两个数，不足 3 个，无需遍历）。
- 回溯状态恢复：递归后必须撤销选择（sum -= i + path.remove()），否则路径和状态会混乱。
- 结果集存储：new ArrayList<>(path) 是因为 path 是引用类型，直接添加会导致后续修改覆盖结果，需新建列表。
复杂度分析
