回溯是一种系统的算法技术，通过逐步构建候选解并在确定其无效时放弃它们来找到计算问题的所有（或部分）解。本页面解释了回溯范式、其实现模式以及在编程面试中的常见应用。
回溯是一种算法范式，它使用深度优先搜索方法来探索问题的所有潜在解决方案。它逐步构建解决方案，在任何时候（“回溯”）丢弃不满足问题约束的解决方案并继续搜索。
来源：leetcode/backtracking/GenerateParentheses.java14-34 leetcode/backtracking/Permutations.java14-32
回溯在以下问题中特别有效：
常见问题类型包括
| 问题类型 | 示例 |
|---|---|
| 组合问题 | 排列、组合、子集 |
| 约束满足 | N皇后、数独 |
| 路径查找 | 迷宫求解、骑士之旅 |
| 字符串生成 | 生成有效括号 |
来源：leetcode/backtracking/GenerateParentheses.java1-11 leetcode/backtracking/Permutations.java1-12
大多数回溯解决方案遵循一个通用模式
通用伪代码模板是
function backtrack(currentState, ...):
if (base case reached):
add current solution to result set
return
for (each possible choice):
if (choice is valid):
make choice
backtrack(updated state, ...)
undo choice (backtrack)
来源：leetcode/backtracking/GenerateParentheses.java21-34
让我们来看一个经典的回溯问题：生成 n 对括号的所有有效组合。
给定 n 对括号，编写一个函数来生成所有格式正确的括号组合。
对于 n = 3，输出应为
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
该解决方案涉及通过添加开括号和闭括号来递归构建字符串，同时保持有效性约束
仓库中的实现使用了一个名为 generateParenthesisRecursive 的函数，该函数跟踪
来源：leetcode/backtracking/GenerateParentheses.java14-34 company/google/GenerateParentheses.java14-34
另一个常见的回溯问题是生成一组元素的所有排列。
给定一组不同的数字，返回所有可能的排列。
对于输入 [1,2,3]，输出应为
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
虽然经典的回溯方法会跟踪已使用的元素并递归构建排列，但仓库中的实现采用了一种迭代方法
这种方法从一个空排列开始，通过将每个数字插入到现有部分排列的所有可能位置来迭代地构建所有排列。
来源：leetcode/backtracking/Permutations.java14-32 company/microsoft/Permutations.java14-32 company/linkedin/Permutations.java14-32
了解何时使用回溯与动态规划非常重要
| 功能 | 回溯 | 动态规划 |
|---|---|---|
| 目的 | 找到所有（或部分）解决方案 | 找到最优解 |
| 方法 | 探索所有可能的路径（可能会丢弃一些） | 从重叠子问题构建解决方案 |
| 时间复杂度 | 通常是指数级的 | 通常是多项式级的 |
| 问题类型 | 决策问题，枚举 | 优化问题 |
| 示例 | 生成所有有效括号 | 找到网格中的最短路径 |
UniquePaths 问题展示了动态规划比回溯更有效的一个案例
来源：leetcode/dynamic-programming/UniquePaths.java8-31
回溯算法通常具有指数时间复杂度，因为它们探索许多可能的组合
| 问题 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 生成括号 | O(4^n / √n) | O(n) |
| 排列 | O(n!) | O(n!) |
空间复杂度包括
来源：leetcode/backtracking/GenerateParentheses.java14-34 leetcode/backtracking/Permutations.java14-32
清晰地定义您的状态：您需要跟踪哪些信息才能在每个步骤中做出决策？
识别约束：是什么使部分解决方案有效或无效？
通过剪枝进行优化：尽早放弃无效路径以减少探索。
避免重复工作：适当时考虑使用记忆化。
考虑迭代实现：在某些情况下，迭代方法可能更高效或更清晰，如排列示例所示。
在实现回溯解决方案时，请着重于
来源：leetcode/backtracking/GenerateParentheses.java21-34 leetcode/backtracking/Permutations.java14-32