回溯算法

回溯算法 是一种通过试错的方式寻找问题解的算法。它尝试逐步构建解决方案，如果在构建过程中的某一步发现当前的构建方案不可行，它会回溯（即取消最近一步的选择），然后尝试其他的可能性。这个过程就像是在迷宫中探索路径，当遇到死路时就退回上一个岔路口，选择另一条路继续前进。

核心思想

试探性选择: 在每一步，都面临多个选择，回溯算法会先选择其中一个进行尝试。
逐步构建: 它一步一步地构建可能的解。
可行性判断 (约束条件): 在每一步构建后，都会检查当前的部分解是否满足问题的约束条件。
回溯 (撤销选择): 如果发现当前部分解不可行，则撤销上一步的选择，回到之前的状态，并尝试其他的选择。
终止条件: 当找到一个完整的可行解，或者当所有可能的选择都尝试完毕且没有找到解时，算法终止。

基本步骤

定义问题的解空间： 确定问题的解可能存在的所有可能组合。例如，对于一个排列问题，解空间就是所有可能的排列。
确定约束条件： 定义问题解必须满足的条件。这些条件用于判断当前构建的部分解是否有效。
选择搜索策略 (通常是深度优先搜索 DFS)： 回溯算法通常使用深度优先搜索的方式来遍历解空间。
设计递归函数 (或迭代方式模拟递归)：

递归函数是实现回溯算法的关键。该函数通常包含以下几个部分：
- 基本情况 (终止条件)： 判断是否找到了一个完整的解，或者是否已经遍历完所有可能性但没有找到解。
- 选择步骤： 在当前状态下，有哪些选择可以进行？
- 扩展状态： 对于每个选择，更新状态，并递归调用自身进入下一层搜索。
- 回溯步骤： 在递归调用返回后，需要撤销当前的选择，恢复到之前的状态，以便尝试其他的选择。
剪枝优化 (可选但重要)： 在搜索过程中，如果发现某个部分解已经不可能导致最终解，可以提前结束对该分支的搜索，以提高效率。这称为剪枝。

应用示例

回溯算法可以应用于解决许多经典问题，包括但不限于：

组合问题：
- 组合总和 (Combination Sum): 在一个数字集合中找到所有和为目标值的组合。
- 子集 (Subsets): 找出给定集合的所有子集。
- 电话号码的字母组合 (Letter Combinations of a Phone Number): 给定数字字符串，返回所有可能的字母组合。
排列问题：
- 全排列 (Permutations): 生成给定集合的所有排列。
- 下一个排列 (Next Permutation): 找到给定排列的下一个字典序排列。
图论问题：
- N 皇后问题 (N-Queens Problem): 在 NxN 的棋盘上放置 N 个皇后，使其互不攻击。
- 数独 (Sudoku Solver): 解决数独谜题。
- 迷宫寻路 (Maze Solving): 找到迷宫的路径。
- 图的着色问题 (Graph Coloring): 给图的顶点着色，使得相邻顶点颜色不同。
- 旅行商问题 (Traveling Salesman Problem - TSP) (近似解或小规模问题)： 虽然TSP通常使用更优化的算法，但在小规模情况下，回溯可以找到解。
其他问题：
- 0-1 背包问题 (0-1 Knapsack Problem)： 虽然动态规划更常用，但回溯也可以解决。
- 正则表达式匹配 (Regular Expression Matching) (某些情况)： 复杂的正则表达式匹配问题可以使用回溯解决。
- 解方程 (Solving Equations) (某些类型)： 例如，约束满足问题 (Constraint Satisfaction Problems - CSPs)。

回溯算法模板

回溯法其实就是暴力查找，回溯法解决的问题都可以抽象为树形结构（N叉树）。

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}