回溯函数需保证路径记录与选择撤销对称：漏解因pop_back()未配对，重复因选择范围失控；状态量作参数、输入数据传const引用、path传引用并严格配对push/pop；used数组比find更高效可靠，含重元素时需加同层去重剪枝；n皇后斜线冲突用abs(row-i)==abs(col-queens[i])验证。
回溯函数怎么写才不会漏解或重复
回溯本质是 DFS 枚举，关键在「路径记录」和「选择撤销」是否对称。漏解往往因为 pop_back() 没配对，重复则多因没控制好选择范围（比如全排列用了 for (int i = 0; i 却没用 <code>visited 数组）。
- 子集/组合类问题：用下标
i控制“只能往后选”，避免 [1,2] 和 [2,1] 被当成两个不同组合 - 全排列类问题：必须用
vector<bool> visited</bool>或原地交换 + 回滚，不能只靠下标 - 每次递归前做选择，递归后立刻
pop_back()或swap()恢复——这两步必须严格成对出现
backtrack 的参数设计为什么影响剪枝效率
参数传值还是传引用，直接决定能否提前剪枝。比如 0-1 背包中，若把当前重量 currentWeight 当作局部变量计算，每次递归都得重算；而作为参数传入，就能在进入子树前判断 currentWeight + w[i] > capacity 直接 return。
- 频繁变化的状态量（如和、深度、坐标）建议作为参数传递，便于约束函数快速判断
- 只读的输入数据（如
nums,board）传 const 引用，避免拷贝开销 - 路径容器
path传引用，但注意：若在递归前push_back()，就必须在递归后pop_back()；若想免去手动恢复，可传值（但会多一次 vector 拷贝）
为什么 used 数组比 find(path.begin(), path.end(), nums[i]) != path.end() 更可靠
后者在每次循环里遍历当前路径，时间复杂度从 O(1) 变成 O(n)，全排列总复杂度从 O(n×n!) 恶化到 O(n²×n!)，n=10 就明显卡顿；更麻烦的是，它无法区分重复元素位置——当 nums 含重复值时（如 [1,1,2]），这种写法会生成重复排列。
-
used[i]是 O(1) 查找，且天然绑定索引，能精准控制每个位置是否被用过 - 遇到含重复数字的数组（如全排列 II），还需配合
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;跳过同层等值分支 - 别用
set或find替代used数组，除非你明确接受性能惩罚
N皇后验证冲突为什么用 abs(row - i) == abs(col - queens[i])
这是判断两个皇后是否在同一斜线的最简数学表达。行差和列差绝对值相等，就说明它们在同一条 45° 或 135° 斜线上。写成循环逐格检查不仅慢，还容易漏掉边界条件。
立即学习“C++免费学习笔记（深入）”；
- 每放一个新皇后，只需遍历已放置的
queens[0..row-1]，检查列冲突col == queens[i]和斜线冲突abs(row - i) == abs(col - queens[i]) - 不要用二维数组存棋盘再扫描整行/整列——那是 O(n) 验证，而上述方式是 O(row)
- 斜线公式记不住？画个 4×4 棋盘标两组坐标试试：
(0,0)和(2,2)→abs(0-2)==abs(0-2)成立；(1,3)和(3,1)→abs(1-3)==abs(3-1)也成立
回溯最难的不是写递归，而是判断“什么时候该停、什么时候该剪、什么时候该换路”。这三个动作全靠你在 if 条件里写对逻辑，而不是靠多跑几轮调试猜出来。
