数据结构之回溯算法

一、回溯算法简介

回溯算法（Backtracking）是一种基于递归的穷举搜索算法，核心思想是 “尝试 - 回退 - 再尝试”：从初始状态出发，逐步探索所有可能的路径，当发现当前路径无法满足条件时（剪枝），撤销当前选择（回溯），回到上一步继续探索其他路径，直到找到解或遍历完所有可能。

回溯算法天然适配 “组合、排列、子集、切割、棋盘（如 N 皇后）” 等多选择、多约束的问题，是数据结构与算法中解决 “穷举类” 问题的核心方法。

二、核心要素

回溯算法的执行过程可类比 “走迷宫”：走一步→发现不通→退回来→换方向再走。其核心包含 4 个要素：

要素	说明
路径	已做出的选择（如已选的组合、排列元素，已放置皇后的位置）
选择列表	当前步骤可选择的选项（如剩余未选的元素、皇后可放置的列）
结束条件	到达决策树的叶子节点，路径满足要求（如组合长度达标、排列完成）
剪枝	提前排除无效路径（如重复组合、皇后冲突），减少不必要的穷举（优化核心）

三、应用场景

以下通过 4 类经典问题，讲解回溯算法的具体实现，覆盖 “组合、排列、子集、棋盘” 四大核心场景。

场景 1：组合问题（无重复元素，不考虑顺序）

问题：给定数组nums = [1,2,3]，找出所有长度为 2 的组合（如[1,2]、[1,3]、[2,3]）。核心：组合不考虑顺序，需通过 “起始索引” 避免重复（如选 1 后只选 1 之后的元素）。

场景 2：排列问题（无重复元素，考虑顺序）

问题：给定数组nums = [1,2,3]，找出所有全排列（如[1,2,3]、[1,3,2]、[2,1,3]等）。核心：排列考虑顺序，需通过 “已选集合” 避免重复选择同一元素。

场景 3：子集问题（所有可能的子集，包括空集）

问题：给定数组nums = [1,2,3]，找出所有子集（如[]、[1]、[1,2]、[1,2,3]、[2]等）。核心：子集是 “选或不选” 的结果，结束条件可省略（每次递归都将当前路径加入结果）。

场景 4：棋盘问题（N 皇后，带复杂约束）

问题：N 皇后问题：在 N×N 的棋盘上放置 N 个皇后，使得任意两个皇后不在同一行、同一列、同一斜线，找出所有合法的放置方案。核心：通过剪枝快速排除无效位置（同行 / 同列 / 同斜线），减少穷举次数。

四、案例分享

题目：给定一个整型数组，其中所有元素都各不相同，返回这些元素所有可能的排列。

如[1，2，3]，返回：[[1，2，3]， [1，3，2]， [2，1，3]， [2，3，1]， [3，1，2]， [3，2，1]]。

import java.util.LinkedList; import java.util.List; public class Solution { List<List<Integer>> result = null; List<Boolean> used = null; // p中保存了一个有index个元素的排列，向这个排列末尾添加第index+1个元素 // 获得一个有index+1个元素的排列 void generatePermutation(int[] nums, int index, List<Integer> p) { if (index == nums.length) { result.add(new LinkedList<>(p)); return; } for (int i = 0; i < nums.length; ++i) if (!used.get(i)) { // 将nums[i]添加到p中 p.add(nums[i]); used.set(i, true); // 递归 generatePermutation(nums, index + 1, p); // 下面两行实现回溯，因为以后还会使用到nums[i]，是逐个元素进行回溯 p.remove(p.size() - 1); used.set(i, false); } return; } // 46 使用递归和回溯的算法完成该题 public List<List<Integer>> permute(int[] nums) { result = new LinkedList<List<Integer>>(); if (nums.length == 0) return result; LinkedList<Integer> p = new LinkedList<>(); used = new LinkedList<>(); // 初始化used for (int i = 0; i < nums.length; ++i) used.add(i, false); generatePermutation(nums, 0, p); return result; } public static void main(String[] args) { int[] nums = { 1, 2, 3 }; System.out.println(new Solution().permute(nums)); } }