回溯算法（Backtracking）常被称为“通用的解题法”。如果把解决一个问题比作走迷宫，回溯算法就是那个不撞南墙不回头的勇者。
什么是回溯算法？
从本质上讲，回溯是一种深度优先搜索（DFS）。它的核心思想是：在搜索过程中，当发现当前的路径已经不能满足求解条件时，就“回退”到上一步，换一条路径继续试探。
核心三个步骤（回溯模板）：
- 路径（Path）： 已经做出的选择。
- 选择列表（Options）： 当前可以做的选择。
- 结束条件（Termination）： 到达决策树底层，无法再做选择的条件。
伪代码框架
func permute(nums []int) [][]int {
var results [][]int
var path []int
used := make([]bool, len(nums)) // 状态标记数组
// 声明闭包函数，以便递归调用
var backtrack func()
backtrack = func() {
// 终止条件：路径长度等于输入数组长度
if len(path) == len(nums) {
// 重点：Go 的 slice 是引用传递，必须 copy 一份快照
results = append(results, append([]int(nil), path...))
return
}
for i := 0; i < len(nums); i++ {
// --- 剪枝：如果已经使用过该元素，跳过 ---
if used[i] {
continue
}
// 做选择
used[i] = true
path = append(path, nums[i])
// 递归进入下一层
backtrack()
// 撤销选择（回溯）
path = path[:len(path)-1]
used[i] = false
}
}
backtrack()
return results
}
为什么我们要“撤销选择”？
这是回溯算法的灵魂。因为我们是在同一套变量（比如一个数组）上进行操作，如果不撤销刚才的操作，当你退回到上一层节点去走另一条分支时，之前的脏数据会干扰新的搜索。
示例
给你的挑战：全排列问题
既然掌握了理论，咱们直接上实战。这是一道非常经典的入门题，能帮你快速建立“回溯感”。
题目描述：
给定一个不含重复数字的数组 nums（例如 [1, 2, 3]），请你返回其所有可能的全排列。
- 输入：
nums = [1, 2, 3] - 输出：
[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
小提示： > 你需要一个
used数组或集合来标记哪些数字已经被填入当前的路径中了，这样下一层递归就不会重复选它。