c#大数据处理问题，选最少的行数使所有的列都至少有1个0，输出最少行所有的组合

Question

| |1|2|3|
|A | 0 | 1 |0 |
|B| 1 | 0 | 1 |
|C |1 | 0 | 0 |
|D| 0 | 1 | 0 |
从ABCD中选出最少的行数，使得每一列都有一个0 ，比如选了AC后，就把BD行去掉，
之前数据就变成
|行名|1|2|3|
|A | 0 | 1 0 |
|C |1 |0 |0 |

然后1 2 3列依然都有至少一个0，且小于这个行数的都不满足可使1 2 3列都有一个0，那么AC就是其中一组满足条件的组合

但是如果为100行 20000列类似
|列名|列1|列2|...列20000|
|A | 0 | 1 |0|1|
|B| 1 | 0 | 1 ||0|
|C |1 | 0 |0 ||1
|D| 0 | 1 | 0|.|0

|行100|0|1|0|
这种如何处理？要求输出所有符合条件的组合，速度快，占内存小，应该怎么做，可以讲思路，算法，最好用c#写出来

Answer 1

基于Monster 组和GPT的调写：

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int[,] matrix = {
            { 0, 1, 0 },
            { 1, 0, 1 },
            { 1, 0, 0 },
            { 0, 1, 0 }
        };

        int minRows = matrix.GetLength(0);
        var solutions = new List<List<int>>();
        FindCombinations(matrix, new List<int>(), 0, solutions, ref minRows);


        
        // 打印所有解决方案
        foreach(var solution in solutions)
        {
            foreach(var row in solution)
            {
                Console.Write((char)('A' + row));
            }
            Console.WriteLine();
        }
    }

    static void FindCombinations(int[,] matrix, List<int> current, int start, List<List<int>> solutions, ref int minRows)
    {
        if (current.Count > minRows)
            return;

        if (IsValidCombination(matrix, current))
        {
            if (current.Count < minRows)
            {
                solutions.Clear();
                minRows = current.Count;
            }
            solutions.Add(new List<int>(current));
            // 不要在这里返回; 继续寻找其他可能的解决方案
        }

        for (int i = start; i < matrix.GetLength(0); i++)
        {
            current.Add(i);
            FindCombinations(matrix, current, i + 1, solutions, ref minRows);
            current.RemoveAt(current.Count - 1);
        }
    }



    static bool IsValidCombination(int[,] matrix, List<int> combination)
    {
        if (combination.Count == 0) return false;

        for (int col = 0; col < matrix.GetLength(1); col++)
        {
            bool hasZero = false;
            foreach (int row in combination)
            {
                if (matrix[row, col] == 0)
                {
                    hasZero = true;
                    break;
                }
            }
            if (!hasZero) return false;
        }
        return true;
    }
}