回溯算法详解

一、是什么？

回溯算法是一种通过试错寻找问题解决方案的算法。它采用深度优先搜索（DFS）策略，逐步构建候选解，并在发现当前路径无法得到有效解时，回退到上一步尝试其他选择。核心思想是**“尝试-回溯-再尝试”**，常用于解决需要遍历所有可能性的问题。

二、解决什么问题

1. 组合问题
   如：从集合 [1,2,3] 中找出所有大小为 2 的子集（[1,2], [1,3], [2,3]）。
2. 排列问题
   如：字符串 "abc" 的所有排列（"abc", "acb", "bac" 等）。
3. 约束满足问题
   如：N 皇后（放置皇后使其互不攻击）、数独求解。
4. 分割问题
   如：将字符串分割为回文子串的所有可能方式。

三、核心方法

回溯通常通过递归实现，包含三个关键步骤：

1. 选择（Choose）：在当前层做一个选择。
2. 递归（Recurse）：基于当前选择进入下一层决策。
3. 撤销（Unchoose）：回退当前选择，尝试其他选项。

void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        保存结果;
        return;
    }
    
    for (选择 : 选择列表) {
        做选择;
        backtrack(新路径, 新选择列表); // 递归
        撤销选择; // 回溯
    }
}

四、应用场景

问题类型	示例 LeetCode 题目
组合问题	77.组合, 39.组合总和
排列问题	46.全排列, 47.全排列Ⅱ
子集问题	78.子集, 90.子集Ⅱ
分割问题	131.分割回文串
棋盘问题	51.N皇后, 37.解数独

五、Java 示例（全排列问题）

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) {
        // 1. 终止条件：路径包含所有元素
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path)); // 深拷贝
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 2. 跳过已使用的元素
            if (used[i]) continue;

            // 3. 选择当前元素
            used[i] = true;
            path.add(nums[i]);

            // 4. 递归进入下一层
            backtrack(nums, path, used, result);

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

六、重要注意事项

1. 剪枝优化
   通过条件判断提前终止无效分支（如组合总和问题中跳过重复值）。
2. 避免重复解
   对输入排序并使用标记数组（如 boolean[] used）。
3. 深拷贝结果
   添加结果时使用 new ArrayList<>(path) 防止后续修改影响已存结果。
4. 递归深度
   当问题规模较大时，递归可能导致栈溢出，需评估数据规模。
5. 时间复杂度
   通常为指数级（如全排列问题 O(n!)），仅适用于小规模问题。

---

回溯 vs 其他算法

算法	特点	适用场景
回溯	系统性试错，空间复杂度低	所有解/组合问题
动态规划	存储子问题解，避免重复计算	最优解问题（最短路径等）
BFS	按层遍历，找到最短路径	无权图最短路径
贪心算法	局部最优解，不保证全局最优	部分最优化问题

---

总结

1. 分析步骤：
   • 确定问题是否需遍历所有可能解（回溯适用条件）。
   • 定义递归终止条件（如路径长度达标）。
   • 设计单层选择逻辑（循环 + 选择/撤销）。
   • 添加剪枝条件优化效率。
2. 代码框架：

   void backtrack(...) {
       if (end) save_result();
       for (选择 : 选择列表) {
           if (invalid) continue; // 剪枝
           make_choice();
           backtrack(...);
           undo_choice();
       }
   }

3. 关键点：
   路径记录（当前选择）、选择列表（剩余选项）、回溯操作（撤销选择）三者缺一不可。

通过大量练习（如 LeetCode 回溯专题），逐步培养问题抽象能力和剪枝优化直觉。