Data-Structure/Algorithm/BackTracking/readme.md

回溯法（Backtracking）是一种系统地枚举所有可能解的方法，通常用于解决组合、排列、约束满足等问题。它的核心思想是：在搜索问题的解空间时，如果发现当前部分解无法得到最终解，就立即放弃（回溯），避免无谓的计算。

我给你拆开讲：

---

1️⃣ 基本思路

1. 从问题的初始状态开始，尝试每一种可能的选择。

2. 对于每一种选择：

   • 判断是否符合条件（约束）。
   • 如果符合，就继续尝试下一步。
   • 如果不符合，直接放弃（剪枝）。

3. 当到达最终状态时，把解记录下来。

4. 搜索完当前选择后，撤销选择（回到上一步），尝试其他可能。

这个“尝试→失败→撤销→尝试其他”过程就是“回溯”。

---

2️⃣ 典型问题

回溯法适合解决这类问题：

• 排列问题：生成1~n的所有排列。
• 组合问题：从n个元素中选出k个组合。
• 子集问题：生成所有子集。
• 棋盘类问题：N皇后、数独、填字游戏。
• 约束满足问题：图着色、八数码问题等。

---

3️⃣ 模板代码（C++示例）

以N皇后问题为例：

vector<int> queens; // queens[i] = 列号
int n;

bool isValid(int row, int col) {
    for(int i = 0; i < row; i++) {
        int c = queens[i];
        if(c == col || abs(c - col) == row - i)
            return false;
    }
    return true;
}

void backtrack(int row) {
    if(row == n) {
        // 找到一个解
        for(int c : queens) cout << c << " ";
        cout << endl;
        return;
    }
    for(int col = 0; col < n; col++) {
        if(isValid(row, col)) {
            queens.push_back(col); // 选择
            backtrack(row + 1);    // 递归
            queens.pop_back();     // 回溯
        }
    }
}

---

4️⃣ 总结

• 回溯法是一种DFS+剪枝的方法。
• 核心是选择、约束、递归、撤销。
• 常用于枚举问题、组合问题和约束满足问题。

---

如果你愿意，我可以给你画一张回溯法搜索树的示意图，直观理解它是怎么“尝试、失败、回退”的。

你想让我画吗？