回溯算法详解

一、什么是回溯算法？

回溯算法本质是暴力搜索的优化版，属于深度优先搜索（DFS）的一种。

核心思想

一步步尝试选择：从一个起点出发，按规则选择下一个元素
遇到死路就回头：如果当前路径走不通（不满足条件），就撤销上一步选择，回到上一个状态
遍历所有可能：直到找到所有符合条件的解，或者遍历完所有可能性

二、回溯算法的适用场景

适用于需要枚举所有可能的组合/排列/路径的问题，典型场景：

全排列问题
组合求和问题
子集问题
棋盘问题（N皇后、解数独）
字符串分割问题

三、回溯算法通用模板（Java）

所有回溯问题都可以套用这个固定框架：

// 回溯通用模板
void backtrack(参数) {
    // 1. 终止条件：找到一个解 / 走到尽头
    if (满足结束条件) {
        保存结果;
        return;
    }

    // 2. 遍历所有可选的选择
    for (选择 : 所有选择) {
        做选择;           // 把当前选择加入路径
        backtrack(参数);   // 递归继续下一步
        撤销选择;         // 回溯：取消刚才的选择，恢复状态
    }
}

三个核心步骤

做选择
递归深入
撤销选择（回溯）

四、Java 实战示例

示例 1：全排列（最经典回溯题）

题目：给定数组 [1,2,3]，输出所有不重复的全排列。

import java.util.ArrayList;
import java.util.List;

public class Permutations {
    // 保存所有最终结果
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>(); // 临时存储当前路径
        boolean[] used = new boolean[nums.length]; // 标记元素是否被使用
        
        // 启动回溯
        backtrack(nums, path, used, res);
        return res;
    }

    // 回溯核心方法
    private static void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> res) {
        // 终止条件：路径长度 = 数组长度，说明找到一个完整排列
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path)); // 新建集合保存快照，避免引用覆盖
            return;
        }

        // 遍历所有可选元素
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue; // 已使用，跳过

            // 1. 做选择
            used[i] = true;
            path.add(nums[i]);

            // 2. 递归
            backtrack(nums, path, used, res);

            // 3. 撤销选择（回溯）
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

    // 测试
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(permute(nums));
    }
}

运行结果：

[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

示例 2：子集问题

题目：给定数组 [1,2,3]，输出所有子集（包含空集）。

import java.util.ArrayList;
import java.util.List;

public class Subsets {
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return res;
    }

    private static void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        // 子集问题：每一步的路径都是一个有效解
        res.add(new ArrayList<>(path));

        // 从 start 开始遍历，避免重复子集
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]); // 选择
            backtrack(nums, i + 1, path, res); // 递归
            path.remove(path.size() - 1); // 撤销选择
        }
    }

    // 测试
    public static void main(String[] args) {
        int[] nums = {1,2,3};
        System.out.println(subsets(nums));
    }
}

运行结果：

[[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

五、回溯算法核心要点

路径（Path）：当前已经做出的选择
选择列表：当前可以选择的元素
结束条件：无法继续选择 / 已满足题目要求
必须回溯：递归返回后必须撤销选择，否则状态会错乱

总结

回溯算法的核心逻辑：选择 → 递归 → 撤销选择
所有回溯题目都可以套用通用模板
核心是状态回退，保证每一次递归的状态独立
专门解决排列、组合、子集、路径搜索类枚举问题