最近在为完成毕业论文的开题报告，忙的焦头烂额的，几乎没什么时间更新博客了，好在最近差不多快完事了，算是拖更好久了，最近总结了一下完成的力扣的关于 回溯算法 的个人解法和看法，谢谢大家~

当题目描述里出现 “所有组合”、“所有排列” 或 “所有可能的路径” 这类字眼时，回溯（Backtracking） 几乎是第一反应。

回溯的核心思想是：尝试 + 撤销。我们通过递归不断“做选择”，在选择之后继续深入探索；当发现这条路走不通或已经得到一个解时，再“撤销选择”，回到上一步尝试其他可能。

本文总结一个 通用的回溯模板，并结合两道经典 LeetCode 题目（17. 电话号码的字母组合、39. 组合总和）进行完整剖析。

回溯算法通用模板

1. 定义全局结果容器（通常是 List）
2. 编写递归函数
   ├─ 确定参数（固定 / 动态 / 辅助）
   ├─ 确定终止条件
   └─ 实现单层逻辑：选择 → 递归 → 撤销
3. 启动递归（确定初始参数）

下面我们逐层拆解。

1. 静态变量存储结果

static List<T> res = new ArrayList<>();

为什么用 static？ 方便在递归函数中直接访问，避免层层传递。 也可以不使用 static，而是作为类成员变量或通过返回值收集，但 static 更简洁。

注意：提交到 LeetCode 时记得在最后清空或返回副本，防止影响后续测试用例。

2. 编写递归方法

参数设计三要素

递归终止条件

必须明确，否则陷入死循环。

单层逻辑结构

for (选择 in 本层集合) {
    做选择
    递归进入下一层
    撤销选择（回溯）
}

关键点：“做选择 → 递归 → 撤销选择” 必须成对出现。

3. 调用递归函数

backtrack(初始参数...);

重点是 第一次调用时各参数的取值，这决定了整棵递归树的起点。

示例一：17. 电话号码的字母组合

题目链接：LeetCode #17

思路分解

1. 结果容器

   static List<String> res = new ArrayList<>();

2. 递归参数设计

   • digits：输入字符串（固定）

   • sb：当前组合路径（动态）

   • index：当前处理到第几位（辅助）

   void backtrack(String digits, StringBuilder sb, int index)

3. 终止条件

   if (index == digits.length()) {
       res.add(sb.toString());
       return;
   }

4. 单层逻辑

   • 获取当前数字对应的字母串

   • 遍历每个字母：追加 → 递归 → 删除

完整代码

class Solution {
    static List<String> res = new ArrayList<>();
    static Map<Character, String> map = new HashMap<>() {{
        put('2', "abc"); put('3', "def"); put('4', "ghi");
        put('5', "jkl"); put('6', "mno"); put('7', "pqrs");
        put('8', "tuv"); put('9', "wxyz");
    }};
​
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.isEmpty()) return res;
        backtrack(digits, new StringBuilder(), 0);
        List<String> result = new ArrayList<>(res);
        res.clear();
        return result;
    }
​
    private void backtrack(String digits, StringBuilder sb, int index) {
        if (index == digits.length()) {
            res.add(sb.toString());
            return;
        }
​
        char digit = digits.charAt(index);
        String letters = map.get(digit);
        for (char c : letters.toCharArray()) {
            sb.append(c);              // 选择
            backtrack(digits, sb, index + 1); // 递归
            sb.deleteCharAt(sb.length() - 1); // 撤销
        }
    }
}

使用 StringBuilder 比 String 拼接更高效；map 用 Character 作为 key 更直观。

示例二：39. 组合总和（允许重复选择）

题目链接：LeetCode #39

问题难点

• 元素可无限重复使用

• 要求 组合不重复（即 [2,2,3] 和 [2,3,2] 视为相同）

关键技巧：从 start 开始枚举，防止回头

for (int i = start; i < candidates.length; i++) { ... }

这样保证每个位置的元素只从右向左递增选择，避免重复。

思路分解

1. 结果容器

   static List<List<Integer>> res = new ArrayList<>();

2. 递归参数

   • candidates：原始数组

   • path：当前组合

   • target：剩余目标值（推荐！比累计和更清晰）

   • start：本层开始枚举的位置

3. 终止与剪枝

   • target == 0 → 找到一组合法

   • target < 0 → 超出，剪枝

完整代码

class Solution {
    static List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrack(candidates, target, 0, new ArrayList<>());
        List<List<Integer>> result = new ArrayList<>(res);
        res.clear();
        return result;
    }

    private void backtrack(int[] candidates, int remain, int start, List<Integer> path) {
        if (remain == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (remain < 0) return;

        for (int i = start; i < candidates.length; i++) {
            path.add(candidates[i]);
            // 允许重复使用，所以仍从 i 开始
            backtrack(candidates, remain - candidates[i], i, path);
            path.remove(path.size() - 1);
        }
    }
}

为什么用 remain 而不是累计和？ 避免每次遍历 path 求和，性能更优，且逻辑更清晰。

回溯模板总结

class Template {
    static List<T> res = new ArrayList<>();

    public List<T> solve(Input input) {
        backtrack(固定参数, 路径, 辅助参数);
        return new ArrayList<>(res);
    }

    void backtrack(固定, 路径, 辅助) {
        // 终止条件
        if (满足条件) {
            res.add(拷贝路径);
            return;
        }

        // 单层遍历
        for (选择 : 本层集合) {
            if (剪枝条件) continue;

            路径.add(选择);
            backtrack(固定, 路径, 更新辅助);
            路径.removeLast(); // 回溯
        }
    }
}

常见剪枝技巧

写在最后

回溯不是“暴力枚举”，而是 有方向的深度优先搜索 + 剪枝。