C#回溯算法详解：全排列问题从入门到精通（手把手教你用C#实现全排列）

什么是全排列？

全排列是指将一组互不相同的元素按照所有可能的顺序进行排列。例如，数组 [1, 2, 3] 的全排列有：

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

总共有 n! 种排列方式（n 为元素个数）。

回溯算法的核心思想

回溯算法本质上是一种“试错”策略：它尝试每一种可能的选择，并在发现当前路径无法达到目标时，撤销上一步选择（即“回溯”），再尝试其他路径。

回溯三要素：

1. 路径（Path）：已经做出的选择。
2. 选择列表（Choices）：当前可以做的选择。
3. 结束条件（Base Case）：到达决策树的底层，无法再做选择。

C#实现全排列（使用回溯）

下面我们用 C# 编写一个完整的全排列程序。我们将使用 List<int> 存储输入数组，并通过递归回溯生成所有排列。

using System;using System.Collections.Generic;class Program{    static void Main()    {        int[] nums = {1, 2, 3};        List<IList<int>> result = Permute(nums);        Console.WriteLine("全排列结果：");        foreach (var perm in result)        {            Console.WriteLine("[" + string.Join(", ", perm) + "]");        }    }    // 主函数：返回所有全排列    public static List<IList<int>> Permute(int[] nums)    {        List<IList<int>> result = new List<IList<int>>();        List<int> path = new List<int>();        bool[] used = new bool[nums.Length]; // 标记元素是否已使用        Backtrack(nums, path, used, result);        return result;    }    // 回溯函数    private static void Backtrack(        int[] nums,        List<int> path,        bool[] used,        List<IList<int>> result)    {        // 结束条件：路径长度等于原数组长度        if (path.Count == nums.Length)        {            result.Add(new List<int>(path)); // 深拷贝            return;        }        // 遍历所有选择        for (int i = 0; i < nums.Length; i++)        {            if (used[i]) continue; // 跳过已使用的元素            // 做选择            path.Add(nums[i]);            used[i] = true;            // 进入下一层决策            Backtrack(nums, path, used, result);            // 撤销选择（回溯）            path.RemoveAt(path.Count - 1);            used[i] = false;        }    }}

代码解析

让我们逐段理解这段 C#递归回溯 代码：

• used 数组用于记录哪些数字已经被加入当前路径，避免重复使用。
• path 是当前正在构建的排列。
• 当 path.Count == nums.Length 时，说明我们已经选够了 n 个数，此时将当前路径加入结果集。
• 关键在于“做选择 → 递归 → 撤销选择”这一经典回溯模板。

这种写法清晰体现了 排列组合算法 的核心逻辑，非常适合初学者理解和模仿。

运行结果

运行上述程序，控制台将输出：

全排列结果：[1, 2, 3][1, 3, 2][2, 1, 3][2, 3, 1][3, 1, 2][3, 2, 1]

总结

通过本教程，你已经掌握了如何使用 C#回溯算法 解决 全排列实现 问题。回溯法虽然时间复杂度较高（O(n!)），但在没有更优解的情况下，它是解决此类组合问题的可靠方法。

建议你动手敲一遍代码，修改输入数组（如 {1, 2} 或 {'A', 'B', 'C'}），观察输出变化，加深理解。掌握这个模板后，你也能轻松应对子集、组合、N皇后等经典回溯问题！

记住：回溯 = 递归 + 状态重置。多练几次，你就是算法高手！