回溯法
java solution
class Solution {public List<List<Integer>> combinationSum3(int k, int n) {//先创建返回的结果List<List<Integer>> result = new ArrayList<>();//然后开始回溯backtrack(k, n, 1, new ArrayList<>(), result);//返回结果return result;}private void backtrack(int k, int remain, int start, List<Integer> path, List<List<Integer>> result) {//首先判断是否满足条件,如果剩余和等于0且当前组合的长度为k, 添加当前path到result中，然后返回if(path.size() == k && remain == 0) {result.add(new ArrayList<>(path));return;}//然后进行剪枝, 组合长度超过k 或者 remain < 0 时需要剪枝if(path.size() > k || remain < 0) return;//回溯for(int i = start; i <= 9; i++) {path.add(i);//添加之后进行回溯判断backtrack(k, remain - i, i + 1, path, result);path.remove(path.size() - 1);}}
}
一个通用的回溯模板：
✅ 回溯算法的经典模板（Backtracking Template）
void backtrack(参数...) {if (满足合法解的条件) {// 处理合法结果（加入答案列表等）return;}if (触发剪枝条件) {// 过早结束（比如路径过长、和超了等）return;}for (int i = 起始位置; i <= 边界; i++) {// 做选择路径.add(i);// 递归，进入下一层决策树backtrack(...);// 撤销选择（回溯）路径.remove(路径.size() - 1);}
}
🧠 关键步骤详解：
① 判断合法结果：
if (路径.size() == k && remain == 0)
这个时候你已经找到了一个完整的结果，可以加入答案。
② 剪枝条件（终止非法路径）：
if (路径.size() > k || remain < 0)
当路径已经无效（长度超了或者和超了），就不需要继续递归了，直接 return。
③ 遍历所有可能选项：
for (int i = start; i <= 9; i++)
依次尝试选取每一个可能的数字。
④ 做选择：
path.add(i)
当前这个数加入路径。
⑤ 回溯递归：
backtrack(...)
进入下一层决策树。
⑥ 撤销选择（回溯）：
path.remove(path.size() - 1)
关键操作：撤回上一次的选择，回到上一步的状态，尝试新的可能。
✅ 常见题目都能用这个套路，比如：
- 组合问题（如本题）
- 排列问题（比如 Leetcode 46/47）
- 子集问题
- 数独、N皇后、迷宫路径
- 分割字符串、括号生成…
