C#回溯算法实现包含五种方法：一、N皇后递归回溯，用布尔数组标记列与对角线；二、N皇后位运算优化，用整数掩码高效判断；三、全排列交换法，原地交换并恢复；四、全排列路径+选择列表法，用path和used数组；五、去重全排列，在排序基础上跳过重复未用元素。
如果您需要在C#中实现回溯算法来处理约束满足类问题，例如N皇后和全排列，则需基于递归与状态试探-撤销机制构建解空间树。以下是针对这两个经典问题的多种独立实现方法：
一、N皇后问题的递归回溯实现
该方法通过逐行放置皇后，并在每一步检查列、主对角线和副对角线是否冲突，若无冲突则递归进入下一行；回溯时恢复当前行的状态以尝试其他列位置。
1、定义全局布尔数组记录列占用状态：bool[] cols = new bool[n];
2、定义布尔数组记录主对角线（row - col 为定值）占用状态：bool[] diag1 = new bool[2 * n - 1];
3、定义布尔数组记录副对角线（row + col 为定值）占用状态：bool[] diag2 = new bool[2 * n - 1];
4、编写递归函数 Solve(row)，当 row == n 时将当前棋盘快照加入结果列表；否则遍历当前行所有列 j，若 cols[j]、diag1[row - j + n - 1]、diag2[row + j] 均为 false，则设置对应标志为 true，递归调用 Solve(row + 1)，之后将三者重置为 false。
二、N皇后问题的位运算优化回溯实现
利用整数的二进制位表示列与对角线的占用状态，通过位移与位与操作高效判断可用位置并更新状态，显著减少空间开销与判断耗时。
1、使用三个 int 变量分别表示列、主对角线、副对角线的占用掩码：int columns = 0, diag1 = 0, diag2 = 0;
2、计算当前行所有可放置位置：int available = (~(columns | diag1 | diag2)) & ((1
3、使用 while (available != 0) 循环，每次取最低位：int pos = available & (-available);
4、更新掩码：columns |= pos; diag1 |= pos > 1;
5、递归调用后恢复掩码：columns ^= pos; diag1 ^= pos > 1;
三、全排列问题的交换回溯实现
该方法在原数组上进行元素交换，递归固定前 i 个位置，对剩余位置进行全排列；每次递归返回后交换回原位置，保证后续分支不受干扰。
1、定义递归函数 Permute(int[] nums, int start)，当 start == nums.Length 时将当前数组拷贝加入结果列表。
2、从 start 开始遍历至末尾索引 end，执行 swap(nums[start], nums[i])；
3、递归调用 Permute(nums, start + 1)；
4、执行 swap(nums[start], nums[i]) 恢复原序。
四、全排列问题的路径+选择列表回溯实现
维护一个路径列表 path 记录当前已选元素，以及一个布尔数组 used 标记各索引是否已被选择；每次递归中遍历所有未使用索引，将其加入 path 并标记为已用，递归后移除并重置标记。
1、初始化空 List
2、定义递归函数 Backtrack()，当 path.Count == nums.Length 时添加新排列到结果中。
3、循环遍历 i 从 0 到 nums.Length - 1，若 used[i] 为 false，则将 nums[i] 加入 path，设 used[i] = true；
4、调用 Backtrack()；
5、从 path 移除最后一个元素，设 used[i] = false。
五、全排列问题的去重版本（含重复元素）实现
当输入数组存在重复元素时，需避免生成相同排列；通过排序预处理 + 跳过相邻相同且前一个未被使用的元素来实现剪枝。
1、对输入数组 nums 进行升序排序：Array.Sort(nums);
2、在路径+选择列表方法基础上，在 for 循环内添加判断：if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
3、其余步骤与第四种方法一致，包括 used 标记、path 添加与回溯撤销。
