布尔矩阵最小行覆盖求解、行组合枚举及高效优化算法问询

假设在布尔矩阵m中，1随机分布在各行中，示例如下：

> set.seed(1)

> (m <- matrix(+(runif(30) > 0.6), 6))
     [,1] [,2] [,3] [,4] [,5]
[1,]    0    1    1    0    0
[2,]    0    1    0    1    0
[3,]    0    1    1    1    0
[4,]    1    0    0    0    0
[5,]    0    0    1    1    1
[6,]    1    0    1    0    0

基于上述示例，有两个问题：

1. 如何高效计算出使得所得子矩阵每列至少包含一个1的最小行数？
2. 如何高效枚举所有满足该条件的子矩阵对应的行？

想到的第一种方法是使用combn函数，暴力解法示例如下：

f <- function(m) {
    n <- nrow(m)
    for (k in 1:n) {
        u <- combn(n, k, \(...) list(
            flag = all(colSums(m[..., , drop = FALSE]) > 0),
            idx = c(...)
        ), simplify = FALSE)
        lst <- Filter(\(x) x$flag, u)
        if (length(lst) > 0) {
            return(
                list(
                    minReqNrOfRows = k,
                    allCombos = lapply(lst, `[[`, "idx")
                )
            )
        }
    }
}

运行结果显示，至少需要3行（例如子矩阵m[c(1,4,5),]的每列都至少有一个1），共有6种这样的行组合：

> f(m)
$minReqNrOfRows
[1] 3

$allCombos
$allCombos[[1]]
[1] 1 4 5

$allCombos[[2]]
[1] 1 5 6

$allCombos[[3]]
[1] 2 4 5

$allCombos[[4]]
[1] 2 5 6

$allCombos[[5]]
[1] 3 4 5

$allCombos[[6]]
[1] 3 5 6

当矩阵行数较多时，combn暴力法的计算量极大。

是否存在更先进的算法可以避免遍历所有可能的行组合？比如动态规划或回溯法，希望能得到相关思路提示。

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