掌握Java回溯算法（从零开始的回溯法教程）

回溯算法的三大要素

1. 路径（Path）：已经做出的选择。
2. 选择列表（Choices）：当前可以做的选择。
3. 结束条件（Base Case）：到达决策树的底层，无法再做选择。

回溯算法模板（Java版）

下面是一个通用的回溯算法框架，适用于大多数问题：

void backtrack(List<List<Integer>> result,                 List<Integer> path,                 int[] choices) {    // 结束条件    if (满足结束条件) {        result.add(new ArrayList<>(path));        return;    }    // 遍历所有可选路径    for (int i = 0; i < choices.length; i++) {        // 做选择        path.add(choices[i]);                // 进入下一层决策        backtrack(result, path, choices);                // 撤销选择（回溯）        path.remove(path.size() - 1);    }}

实战案例：全排列问题

我们以经典的“全排列”问题为例：给定一个不含重复数字的数组，返回其所有可能的全排列。

例如：输入 [1,2,3]，输出 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]。

以下是完整的Java代码实现：

import java.util.*;public class Permutations {    public List<List<Integer>> permute(int[] nums) {        List<List<Integer>> result = new ArrayList<>();        List<Integer> path = new ArrayList<>();        backtrack(result, path, nums, new boolean[nums.length]);        return result;    }    private void backtrack(List<List<Integer>> result,                         List<Integer> path,                         int[] nums,                         boolean[] used) {        // 结束条件：路径长度等于数组长度        if (path.size() == nums.length) {            result.add(new ArrayList<>(path));            return;        }        // 尝试每一个数字        for (int i = 0; i < nums.length; i++) {            // 跳过已使用的数字            if (used[i]) continue;            // 做选择            path.add(nums[i]);            used[i] = true;            // 递归进入下一层            backtrack(result, path, nums, used);            // 撤销选择（关键！）            path.remove(path.size() - 1);            used[i] = false;        }    }    // 测试主函数    public static void main(String[] args) {        Permutations p = new Permutations();        int[] nums = {1, 2, 3};        System.out.println(p.permute(nums));    }}

为什么需要“撤销选择”？

这是递归回溯的核心！因为 path 是一个引用对象，在递归过程中会被多个分支共享。如果不撤销选择，前面分支的数据会污染后面分支的结果。通过“添加 → 递归 → 删除”的三步操作，保证了每个递归调用栈中的 path 是干净、独立的。

常见应用场景

• 组合问题（如：从 n 个数中选 k 个）
• 排列问题（如：全排列、带重复元素的排列）
• 子集问题（如：求所有子集）
• 棋盘问题（如：N皇后、数独）
• 字符串问题（如：电话号码的字母组合）

总结

通过本篇算法入门教程，你应该已经掌握了 Java 回溯算法的基本思想和实现方式。记住：回溯 = 递归 + 选择 + 撤销。多练习几个经典题目，你会越来越熟练！

建议初学者从“子集”、“组合”这类简单问题入手，逐步挑战“N皇后”等复杂问题。坚持练习，你也能成为算法高手！

关键词回顾：Java回溯算法、回溯法教程、递归回溯、算法入门