如何枚举固定0和1数量的二进制数组所有合法组合？

嘿，这个问题我熟！你想要遍历固定0和1数量的所有二进制数组组合，而不是所有可能的2^n种组合对吧？你的例子里2个0、3个1，总数就是组合数C(5,2)=10种，确实比遍历所有32种组合高效多了。

先说说你现有的代码：那段逻辑其实是模拟二进制数递增，生成所有可能的0/1组合，但这种方法会把大量不符合数量要求的组合也生成出来，当n比较大的时候效率会很低。下面给你两种更高效的方案：

方案1：直接生成符合条件的数组（一次性获取所有结果） #

本质上，这个问题等价于从n个位置中选出k个位置放1，剩下的放0（k是1的数量）。我们可以用回溯法生成所有k个位置的组合，再根据这些位置构造数组，直接得到所有符合要求的结果。

代码示例（JavaScript） #

function generateFixedBinaryArrays(n, numOnes) {
    const result = [];
    
    // 回溯生成所有numOnes个位置的组合
    function backtrack(start, currentIndices) {
        // 当选够了numOnes个位置，构造数组
        if (currentIndices.length === numOnes) {
            const arr = new Array(n).fill(0);
            currentIndices.forEach(idx => arr[idx] = 1);
            result.push(arr);
            return;
        }
        // 从start开始选，避免重复组合
        for (let i = start; i < n; i++) {
            currentIndices.push(i);
            backtrack(i + 1, currentIndices);
            currentIndices.pop();
        }
    }
    
    backtrack(0, []);
    return result;
}

// 测试你的例子：n=5，1的数量是3
const allCombinations = generateFixedBinaryArrays(5, 3);
allCombinations.forEach(arr => console.log(arr.join(',')));

优点 #

• 直接生成目标组合，没有无效计算，效率远高于遍历所有2^n种组合再筛选。
• 一次性得到所有结果，适合需要批量处理的场景。

方案2：逐个生成下一个组合（内存友好） #

如果不需要一次性存储所有组合，而是想逐个处理每个符合条件的数组，用迭代器的方式逐个生成下一个组合会更节省内存，尤其是当n很大的时候。

这个方法基于“下一个字典序组合”的思路，从初始的全后缀1开始，一步步生成下一个符合要求的数组：

代码示例（JavaScript） #

function* iterateFixedBinaryArrays(n, numOnes) {
    // 初始化第一个组合：末尾numOnes个1
    const arr = new Array(n).fill(0);
    for (let i = n - numOnes; i < n; i++) {
        arr[i] = 1;
    }
    yield [...arr];
    
    while (true) {
        let i = n - 1;
        let countOnes = 0;
        // 从右往左数连续的1的数量
        while (i >= 0 && arr[i] === 1) {
            countOnes++;
            i--;
        }
        // 找不到可以调整的0，说明已经遍历完所有组合
        if (i < 0) break;
        
        // 把当前找到的0改成1
        arr[i] = 1;
        // 把后面的countOnes个1移到最右侧，中间补0
        for (let j = i + 1; j < n - countOnes; j++) {
            arr[j] = 0;
        }
        for (let j = n - countOnes; j < n; j++) {
            arr[j] = 1;
        }
        
        yield [...arr];
    }
}

// 测试：逐个遍历并打印
for (const arr of iterateFixedBinaryArrays(5, 3)) {
    console.log(arr.join(','));
}

优点 #

• 内存占用极低，每次只维护一个数组实例。
• 按需生成下一个组合，适合流式处理的场景。

对比你原有的代码 #

你原来的代码是遍历所有2^{n种组合，如果要适配需求，需要在循环里添加筛选逻辑（比如统计数组中1的数量是否等于目标值），但这种方法在n较大时会做大量无用功。比如n=20，k=10，C(20,10)=184756，而2}20=1048576，需要遍历百万次才能得到18万有效结果，效率差距非常明显。

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