算法面试题：回溯算法

1. 回溯算法的核心思想是什么？

• 通过递归遍历所有可能解。
• 在不满足条件时回退（剪枝）。
• 适合排列组合、子集搜索、棋盘问题。

2. 常见回溯题型有哪些？

• 全排列、组合。
• 子集和、括号生成。
• 数独、N 皇后。

3. 剪枝策略有哪些？

• 提前判断不可能满足的分支。
• 使用约束条件减少搜索空间。
• 根据问题特性优化递归顺序。

4. 回溯与深度优先搜索有什么区别？

• 回溯是一种特殊的 DFS，带有回退和解空间恢复机制。
• DFS 侧重遍历结构，回溯侧重搜索解。

5. 你如何表示回溯状态？

• 使用路径数组或布尔标记。
• 记录当前选择和剩余资源。

6. 回溯的时间复杂度通常是多少？

• 取决于解空间大小。
• 通常为指数级，O(n!) 或 O(2^n) 等。

7. 什么时候回溯可以接受？

• 数据规模较小或问题结构有限制。
• 需要枚举满足条件的所有解。

8. 如何优化回溯实现？

• 添加剪枝条件。
• 使用缓存或记忆化避免重复计算。
• 优先搜索更有可能成功的分支。