JAVA：实现回溯算法的技术指南

1、简述

回溯算法（Backtracking）是解决 组合、排列、约束满足问题 的常用方法。它的本质是一种 搜索算法，通过 “尝试 → 判断 → 回退” 的过程，寻找问题的所有解或最优解。

在面试和实际开发中，回溯常用于：

✨ 排列组合问题（如全排列、子集生成）

✨ 约束问题（如 N 皇后、数独求解）

✨ 路径搜索问题（如迷宫、图的遍历）

2、实现思想

核心公式：

for (选择 in 可选列表):
    做选择
    递归调用（进入下一层）
    撤销选择（回退）

特点：

✨ 递归：通过递归函数深入搜索。

✨ 回退：当路径不满足条件时回退，尝试其他可能。

✨ 剪枝：提前排除不可能的分支，提高效率。

3、实践样例

案例1：全排列问题

问题：给定一个数组 [1, 2, 3]，输出所有排列结果。

import java.util.*;

public class Permutations {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, new ArrayList<>(), new boolean[nums.length], result);
        return result;
    }

    private void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> result) {
        // 递归结束条件
        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(nums, path, used, result); // 递归

            // 回退
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        Permutations p = new Permutations();
        int[] nums = {1, 2, 3};
        List<List<Integer>> result = p.permute(nums);
        System.out.println("全排列结果：" + result);
    }
}

输出结果

全排列结果：[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

案例2：N 皇后问题

问题：在 N×N 的棋盘上放置 N 个皇后，要求任意两个皇后不在同一行、同一列、同一对角线上。

import java.util.*;

public class NQueens {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> results = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        backtrack(board, 0, results);
        return results;
    }

    private void backtrack(char[][] board, int row, List<List<String>> results) {
        if (row == board.length) {
            results.add(construct(board));
            return;
        }

        for (int col = 0; col < board.length; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                backtrack(board, row + 1, results);
                board[row][col] = '.'; // 回退
            }
        }
    }

    private boolean isValid(char[][] board, int row, int col) {
        // 检查列
        for (int i = 0; i < row; i++) if (board[i][col] == 'Q') return false;
        // 检查左上对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
            if (board[i][j] == 'Q') return false;
        // 检查右上对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++)
            if (board[i][j] == 'Q') return false;
        return true;
    }

    private List<String> construct(char[][] board) {
        List<String> path = new ArrayList<>();
        for (char[] row : board) path.add(new String(row));
        return path;
    }

    public static void main(String[] args) {
        NQueens nQueens = new NQueens();
        List<List<String>> results = nQueens.solveNQueens(4);
        System.out.println("4 皇后解法数量：" + results.size());
        results.forEach(System.out::println);
    }
}

输出结果

4 皇后解法数量：2
[.Q.., ...Q, Q..., ..Q.]
[..Q., Q..., ...Q, .Q..]

4、时间复杂度

✨ 全排列：O(n!)

✨ N 皇后：大约 O(N!)

✨ 子集问题：O(2^n)

因此，回溯适合规模不大的问题，或者结合 剪枝优化 提升性能。

5、总结

✨ 回溯算法的本质是 深度优先搜索 + 回退。

✨ 它广泛应用于 排列组合、约束问题、路径搜索 等场景。

✨ 关键是 递归 + 回退 的代码模板：

for (选择 in 可选列表):
    做选择
    递归调用
    撤销选择

✨ 实际应用中，常结合 剪枝 提升效率。

📌 今天你学会了：

✨ ✅ 回溯算法的思想

✨ ✅ 全排列案例

✨ ✅ N 皇后案例

✨ ✅ 时间复杂度与优化思路