如何编写通用方法生成任意数量灯指定点亮数的所有组合

核心思路 #

我们需要实现的是经典的无重复组合生成逻辑，不需要手动堆叠嵌套for循环，用递归即可适配任意总数量n、选取数量k的场景：

• 每次决策对应当前位置的灯是否选中：
  • 如果选中当前灯，接下来只需要从后面的灯里选k-1个即可
  • 如果不选中当前灯，接下来从后面的灯里选k个
• 终止条件为选取数量k减到0，此时记录当前的组合结果

通用C#实现代码 #

using System.Collections.Generic;

public static class CombinationGenerator
{
    // 生成从1到n中选k个的所有组合
    public static List<List<int>> GenerateCombinations(int n, int k)
    {
        List<List<int>> result = new List<List<int>>();
        Backtrack(n, k, 1, new List<int>(), result);
        return result;
    }

    // 递归回溯核心逻辑
    private static void Backtrack(int n, int remain, int start, List<int> current, List<List<int>> result)
    {
        if (remain == 0)
        {
            result.Add(new List<int>(current));
            return;
        }
        // 剪枝优化：剩余可选数量不足时直接终止循环
        for (int i = start; i <= n - remain + 1; i++)
        {
            current.Add(i);
            Backtrack(n, remain - 1, i + 1, current, result);
            current.RemoveAt(current.Count - 1);
        }
    }
}

原有场景兼容用法 #

你原来10盏灯选1或2个的需求，直接调用该方法合并结果即可，输出和你原有代码完全一致：

List<string> lstAllOptions = new List<string>();

// 选1盏的情况
var comb1 = CombinationGenerator.GenerateCombinations(10, 1);
foreach (var c in comb1)
{
    lstAllOptions.Add(c[0].ToString());
}

// 选2盏的情况
var comb2 = CombinationGenerator.GenerateCombinations(10, 2);
foreach (var c in comb2)
{
    lstAllOptions.Add($"{c[0]} and {c[1]}");
}

大组合数场景优化 #

如果你需要处理类似43选19这类组合数极大的场景（C(43,19)约为1.9亿），全量加载到内存会占用极高资源，建议改成迭代器版本边生成边处理：

public static IEnumerable<List<int>> GenerateCombinationsLazy(int n, int k)
{
    return BacktrackLazy(n, k, 1, new List<int>());
}

private static IEnumerable<List<int>> BacktrackLazy(int n, int remain, int start, List<int> current)
{
    if (remain == 0)
    {
        yield return new List<int>(current);
        yield break;
    }

    for (int i = start; i <= n - remain + 1; i++)
    {
        current.Add(i);
        foreach (var combination in BacktrackLazy(n, remain - 1, i + 1, current))
        {
            yield return combination;
        }
        current.RemoveAt(current.Count - 1);
    }
}

使用的时候直接遍历即可，不需要等待所有组合生成完成：

foreach (var comb in CombinationGenerator.GenerateCombinationsLazy(43,19))
{
    // 直接处理当前组合，无需全量存储
}

内容的提问来源于stack exchange，提问作者FaceHoof