回溯搜索

回溯是在状态空间树上进行的 DFS。每层选择一个候选决策，进入下一层；返回时撤销这次选择，使程序恢复到选择前的状态。它适用于枚举排列、组合、棋盘摆放和所有满足约束的方案。

1. 三步模式：选择、递归、撤销

回溯的关键不是“递归”本身，而是状态恢复必须完整。当前路径 path、已使用标记 used 和棋盘占用信息，都应在递归返回后恢复。

vector<int> path;
vector<bool> used;

void dfs(int depth, int n) {
    if (depth == n) {
        output(path);              // 得到一个完整方案
        return;
    }
    for (int x = 1; x <= n; ++x) {
        if (used[x]) continue;
        used[x] = true;            // 选择
        path.push_back(x);
        dfs(depth + 1, n);         // 搜索下一层
        path.pop_back();           // 撤销
        used[x] = false;
    }
}

这段程序枚举 1..n 的全部排列。若题目只需判断是否存在方案，可以在找到答案后向上返回 true，及时停止搜索。

2. 状态设计与终止条件

先明确每一层“决定什么”：排列的第 depth 位、组合中当前考虑的位置，或 N 皇后的第几行。终止条件表示已构成完整候选；此时只记录满足要求的方案。候选生成必须保证不漏、不重，并在进入下一层前检查局部约束。

void choose(int start, int k, int n) {
    if (path.size() == k) {
        output(path);
        return;
    }
    for (int x = start; x <= n; ++x) {
        path.push_back(x);
        choose(x + 1, k, n);       // 递增起点，避免组合重复
        path.pop_back();
    }
}

3. 剪枝

剪枝是指尽早放弃不可能产生答案的分支。可行性剪枝排除违反规则的状态，例如皇后冲突；数量剪枝在剩余元素不足以补齐答案时返回；最优性剪枝在当前代价已不优于已知答案时停止。剪枝只能删去确定无用的分支，不能改变所有合法解的集合。

// 还需要 need 个数，但区间 [x, n] 的元素已不足
if (n - x + 1 < need) return;

// N 皇后：同列或同对角线冲突便不递归
if (col[c] || diag1[r - c + n] || diag2[r + c]) continue;

4. 复杂度与常见错误

回溯复杂度由搜索树决定。全排列有 n! 个叶子，若输出每个长度为 n 的排列，总时间为 O(n·n!)；递归栈、路径和标记通常占 O(n)，不计保存的答案。

常见错误包括：忘记 pop_back() 或撤销标记、在递归后修改了错误的状态、组合仍从 1 开始枚举导致重复，以及把图 DFS 的永久访问标记误用于路径枚举。调试时可打印每层路径，核对进入和返回后的状态是否一致。