1. 核心思想：有路就走，走不通就退回来

回溯算法的本质是一种有组织的、系统性的暴力搜索，它基于深度优先搜索 (Depth-First Search, DFS)。但它比纯粹的暴力搜索要聪明得多，因为它懂得 “剪枝”。

我们可以用一个生动的比喻来理解：

走迷宫： 假设你站在一个巨大迷宫的入口，你的目标是找到出口。你手里没有地图，只能一步步探索。

• 回溯策略：
  1. 你站在一个路口，面前有多条岔路。
  2. 你随便选择一条路，一直走下去。
  3. 在前进的过程中，你会在走过的路上做标记（比如撒面包屑），这样你就知道哪些路已经走过了。
  4. 当你走到一个死胡同（不满足条件，无法继续前进），或者发现这条路不是你要找的出口时，你会怎么做？
  5. 你会原路返回到上一个你做选择的岔路口。这个“返回”的动作，就是 “回溯” (Backtrack)。
  6. 回到上一个岔路口后，你会擦掉刚才做的标记（收回面包屑），然后尝试选择另一条你没走过的岔路。
  7. 你不断重复这个“选择-前进-回溯-换选择”的过程，直到你系统地探索完所有可能的路径，或者找到了一个或所有出口。

这个比喻揭示了回溯算法的几个关键要素：

• 路径 (Path)：你已经做出的一系列选择。
• 选择列表 (Choices)：在当前状态下，你还可以做的选择。
• 终止条件 (Termination)：什么时候算找到了一条完整的路径（例如，找到了迷宫出口）。
• 剪枝 (Pruning)：什么时候发现当前路径是“死胡同”，需要提前回溯。

2. 回溯法与解空间树

回溯算法的搜索过程，可以被可视化为对一棵 “解空间树” (State-Space Tree) 的遍历。

• 树的根节点：代表搜索的初始状态。
• 树的节点：代表在搜索过程中达到的某个状态（做出了一系列选择）。
• 树的边：代表在某个状态下做出的一个选择。
• 树的叶子节点：代表一条完整的路径，可能是问题的解，也可能不是。

回溯算法就是在解空间树上进行深度优先搜索。

• 前进：从父节点走向子节点。
• 回溯：当发现子节点不满足条件时，从子节点退回到父节点。

剪枝 (Pruning) 这是回溯法与暴力穷举（纯DFS）的关键区别。剪枝函数（或限界函数）的作用是，在遍历解空间树时，提前判断一个子树是否可能包含问题的解。如果不可能，就直接“剪掉”整个子树，不再进行搜索。这可以极大地减少搜索空间，提高算法效率。

剪枝的类型：

• 约束函数：根据问题给定的显式约束条件进行剪枝。例如，在N皇后问题中，如果当前位置的列或对角线已经有皇后，就不能再放。
• 限界函数：通常用于优化问题（如求最优解）。如果当前已生成的路径成本已经超过了当前找到的最优解，那么这条路径及其子树就不可能产生更优的解，可以剪枝。

3. 回溯算法的通用模板

几乎所有的回溯问题，都可以用一个非常相似的递归模板来解决。理解并掌握这个模板至关重要。

// result 用来存放所有符合条件的解
vector<vector<DataType>> result; 
 
// path 用来存放当前已经做出的一条路径
vector<DataType> path;
 
void backtrack(选择列表, path) {
    // 1. 终止条件：判断当前 path 是否是一个完整的解
    if (满足终止条件) {
        result.push_back(path); // 收集解
        return; // 结束当前递归
    }
 
    // 2. 遍历当前状态下的所有可选选择
    for (选择 in 选择列表) {
        
        // 3. 剪枝操作 (可选，但非常重要)
        if (当前选择不合法 or 无法导向最优解) {
            continue; // 跳过这个选择
        }
 
        // 4. 做出选择
        // 将当前选择添加到路径中
        path.push_back(选择);
 
        // 5. 进入下一层决策
        // 递归调用 backtrack，传入更新后的选择列表和路径
        backtrack(更新后的选择列表, path);
 
        // 6. 撤销选择 (回溯)
        // 将刚才添加的选择从路径中移除，恢复到之前的状态
        // 这样才能不影响同层其他分支的搜索
        path.pop_back();
    }
}

对模板的解读：

• 递归函数的参数：通常需要包含“当前可做的选择列表”和“当前已走过的路径”。
• for 循环：代表在当前层级（解空间树的某个节点），你可以尝试的所有可能性（所有分支）。
• 递归调用 backtrack(...)：深入到下一层级（走向子节点）。
• path.pop_back()：这是回溯的精髓。当一个分支的 backtrack 调用结束后（无论是找到了解还是走到了死胡同），程序会回到 for 循环的当前层。pop_back() 操作就像是把撒出去的面包屑收回来，将状态恢复到做出该选择之前，以便接下来可以尝试 for 循环中的下一个选择（探索另一个兄弟分支）。

4. 经典应用案例

a) 全排列 (Permutations)

• 问题：给定一个不含重复数字的数组，返回其所有可能的全排列。
• 路径：一个已经形成的排列的一部分。
• 选择列表：数组中还没有被使用过的数字。
• 终止条件：路径的长度等于原数组的长度。
• 回溯：将刚加入排列的数字移除，并标记为“未使用”。

b) 组合 (Combinations)

• 问题：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
• 路径：一个已经形成的组合。
• 选择列表：从某个起始数到 n 的所有数字。
• 终止条件：路径的长度等于 k。
• 剪枝：如果剩余可选的数字数量已经不足以凑成一个 k 个数的组合，就可以提前剪枝。

c) N皇后问题 (N-Queens)

• 问题：在 N×N 的棋盘上放置 N 个皇后，使其不能互相攻击。
• 路径：已经放置好的几行皇后的位置。
• 选择列表：在当前行，所有可以放置皇后的列。
• 终止条件：成功放置了 N 行皇后。
• 剪枝：在尝试放置 (row, col) 位置的皇后时，检查该位置的列、主对角线、副对角线是否已被其他皇后占据。如果被占据，则该选择不合法，直接跳过。

5. 总结