C#排列组合详解（递归与非递归实现全攻略）

什么是排列与组合？

• 排列（Permutation）：从 n 个不同元素中取出 m 个元素，按照一定顺序排成一列。顺序不同视为不同结果。
• 组合（Combination）：从 n 个不同元素中取出 m 个元素，不考虑顺序。只关心选了哪些元素。

例如，从 [A, B, C] 中取 2 个：

• 排列有：AB, BA, AC, CA, BC, CB（共 6 种）
• 组合有：AB, AC, BC（共 3 种）

一、递归实现排列组合

递归是一种“自己调用自己”的编程技巧，非常适合解决排列组合这类具有重复子结构的问题。

1.1 递归实现全排列

下面是一个使用递归生成数组全排列的 C# 示例：

using System;using System.Collections.Generic;class Program{    static void Main()    {        int[] nums = { 1, 2, 3 };        List<int> current = new List<int>();        List<List<int>> result = new List<List<int>>();        bool[] used = new bool[nums.Length];        GeneratePermutations(nums, current, result, used);        foreach (var perm in result)        {            Console.WriteLine(string.Join(", ", perm));        }    }    static void GeneratePermutations(        int[] nums,        List<int> current,        List<List<int>> result,        bool[] used)    {        // 递归终止条件：当前路径长度等于原数组长度        if (current.Count == nums.Length)        {            result.Add(new List<int>(current));            return;        }        for (int i = 0; i < nums.Length; i++)        {            if (!used[i])            {                used[i] = true;                current.Add(nums[i]);                GeneratePermutations(nums, current, result, used);                current.RemoveAt(current.Count - 1); // 回溯                used[i] = false;            }        }    }}

这段代码通过“回溯法”实现全排列，核心思想是：选择一个未使用的数字 → 加入当前路径 → 递归 → 撤销选择。这就是经典的 递归实现排列组合 方法。

1.2 递归实现组合

组合不需要考虑顺序，因此我们只需确保每次选择的元素索引递增即可：

static void GenerateCombinations(    int[] nums,    int start,    int k,    List<int> current,    List<List<int>> result){    if (current.Count == k)    {        result.Add(new List<int>(current));        return;    }    for (int i = start; i < nums.Length; i++)    {        current.Add(nums[i]);        GenerateCombinations(nums, i + 1, k, current, result);        current.RemoveAt(current.Count - 1);    }}// 调用示例：从 [1,2,3] 中选 2 个int[] nums = { 1, 2, 3 };List<int> current = new List<int>();List<List<int>> result = new List<List<int>>();GenerateCombinations(nums, 0, 2, current, result);

二、非递归实现排列组合

虽然递归写法简洁，但在数据量大时可能造成栈溢出。因此，掌握 非递归排列组合 实现也很重要。

2.1 非递归实现全排列（字典序法）

我们可以使用“下一个排列”算法，按字典序生成所有排列：

using System;using System.Linq;class Program{    static void Main()    {        int[] nums = { 1, 2, 3 };        Array.Sort(nums); // 初始必须有序        do        {            Console.WriteLine(string.Join(", ", nums));        }        while (NextPermutation(nums));    }    static bool NextPermutation(int[] nums)    {        int i = nums.Length - 2;        while (i >= 0 && nums[i] >= nums[i + 1]) i--;        if (i < 0) return false; // 已是最大排列        int j = nums.Length - 1;        while (nums[j] <= nums[i]) j--;        Swap(nums, i, j);        Reverse(nums, i + 1, nums.Length - 1);        return true;    }    static void Swap(int[] nums, int i, int j)    {        int temp = nums[i];        nums[i] = nums[j];        nums[j] = temp;    }    static void Reverse(int[] nums, int start, int end)    {        while (start < end)        {            Swap(nums, start, end);            start++;            end--;        }    }}

2.2 非递归实现组合（位运算法）

对于组合，我们可以利用二进制位表示是否选择某个元素：

static List<List<int>> GetCombinations(int[] nums, int k){    List<List<int>> result = new List<List<int>>();    int n = nums.Length;    int total = 1 << n; // 2^n 种子集    for (int mask = 0; mask < total; mask++)    {        if (CountBits(mask) == k)        {            List<int> combo = new List<int>();            for (int i = 0; i < n; i++)            {                if ((mask & (1 << i)) != 0)                {                    combo.Add(nums[i]);                }            }            result.Add(combo);        }    }    return result;}static int CountBits(int x){    int count = 0;    while (x != 0)    {        count += x & 1;        x >>= 1;    }    return count;}

三、总结

通过本文，你已经掌握了 C# 中实现排列组合的两种主流方式：

• 递归方法：代码简洁，逻辑清晰，适合理解问题本质；
• 非递归方法：避免栈溢出，效率更高，适合处理大规模数据。

无论你是在准备面试，还是开发实际项目，这些 C#算法教程 中的核心技巧都将为你打下坚实基础。建议多动手练习，尝试修改参数、调试过程，加深理解。

希望这篇关于 C#排列组合 的教程对你有帮助！欢迎收藏、分享，并在评论区留下你的疑问或心得。