回溯法（Backtracking）是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来撤销上一步的选择，这就是“回溯”的含义。它通常用于解决组合问题、排列问题、子集问题、棋盘问题（如N皇后问题）等。
下面我将通过一个简单的例子——解决N个数字的全排列问题，来详细解释回溯法的实现。
### 全排列问题的回溯法实现
假设我们有一个包含n个不同数字的数组，我们想要找出这个数组的所有可能排列。
def permute(nums):
def backtrack(first=0):
# 所有数都填完了
if first == n:
output.append(nums[:])
for i in range(first, n):
# 动态维护数组
nums[first], nums[i] = nums[i], nums[first]
# 继续递归填下一个数
backtrack(first + 1)
# 撤销操作
nums[first], nums[i] = nums[i], nums[first]
n = len(nums)
output = []
backtrack()
return output
# 示例
nums = [1, 2, 3]
print(permute(nums))
### 代码解析
1. **定义回溯函数**：`backtrack`函数是一个嵌套的辅助函数，它接受一个参数`first`，表示当前需要填充的位置。
2. **递归终止条件**：当`first`等于数组的长度`n`时，表示已经找到了一个完整的排列，此时将这个排列的副本添加到结果集中。
3. **循环遍历**：从`first`开始遍历数组，尝试将每个数放到`first`位置。
4. **做选择**：通过交换`nums[first]`和`nums[i]`，将`nums[i]`放到`first`位置。
5. **递归**：继续调用`backtrack(first + 1)`，处理下一个位置。
6. **撤销选择**：在递归返回之前，需要撤销上一步的选择，即将`nums[first]`和`nums[i]`交换回来，以确保在后续的迭代中，数组的状态是正确的。
7. **返回结果**：在外部函数`permute`中，我们初始化结果集`output`为空列表，调用`backtrack()`函数，并返回结果集。
这就是回溯法的一个基本实现。通过不断地选择、递归、撤销选择，我们可以找到问题的所有解。