如何高效系统遍历长度为n（偶数）的平衡二进制字符串？

要高效遍历长度为n（偶数）的平衡二进制字符串（也就是恰好包含n/2个0和n/2个1的串），核心思路是直接生成符合条件的组合，而不是遍历所有二进制串再过滤——后者的时间复杂度是O(2^n)，对于n≥20就已经完全不实用了。

本质上，平衡二进制串等价于从n个位置中选n/2个位置放1（剩下的放0），所以问题转化为生成组合数C(n, n/2)的所有组合。下面是几种最高效的实现方法：

1. 字典序组合生成（Knuth's Algorithm L） #

这是最经典、最通用的高效算法，属于迭代式生成，每个组合的生成 amortized 时间复杂度是O(1)，实现简单且性能稳定。

算法核心步骤（针对选k=n/2个位置的场景）： #

• 初始化组合为最小的字典序序列：[0, 1, ..., k-1]（代表前k个位置放1）
• 重复以下步骤直到无法生成下一个组合：
  1. 找到最右边的索引i，使得a[i] < n - k + i（即这个位置的元素还能增大）
  2. 将a[i]加1
  3. 把a[i+1 ... k-1]设置为a[i]+1, a[i]+2, ...（保证后面的元素是最小的递增序列）
• 每个组合对应一个二进制串：将组合中的位置设为1，其余为0

Python代码示例（生成平衡二进制串）： #

def generate_balanced_binary_strings(n):
    k = n // 2
    # 初始化组合：存储的是放1的位置（从0开始）
    a = list(range(k))
    while True:
        # 转换为二进制串
        bits = ['0'] * n
        for pos in a:
            bits[pos] = '1'
        yield ''.join(bits)
        
        # 找下一个组合（Algorithm L）
        i = k - 1
        while i >= 0 and a[i] == n - k + i:
            i -= 1
        if i < 0:
            break
        a[i] += 1
        for j in range(i+1, k):
            a[j] = a[j-1] + 1

# 测试n=4的情况
for s in generate_balanced_binary_strings(4):
    print(s)
# 输出：0011, 0101, 0110, 1001, 1010, 1100

2. 类格雷码组合生成（相邻组合仅差一个元素） #

如果你的场景需要相邻的平衡二进制串尽可能相似（比如缓存友好、增量计算），可以用类格雷码的组合生成算法。这类算法生成的相邻组合，只需要交换一个0和一个1的位置（对应二进制串的两个位翻转，汉明距离为2），缓存命中率极高。

核心思路： #

通过递归或迭代的方式，每次只修改一个元素的位置，保持组合的大小不变。比如Ehrlich的算法，或者基于位运算的格雷码转换，都能实现这个效果。

优势： #

• 相邻组合的内存变化极小，适合需要连续处理相似数据的场景（比如硬件模拟、动态规划增量计算）
• 同样是O(C(n,k))的时间复杂度，常数因子略高，但缓存友好带来的实际性能可能更好

3. 递归回溯（快速实现小n场景） #

如果n比较小（比如n≤16），递归回溯的实现成本极低，代码简洁易懂，但大n下会有栈开销，效率不如迭代算法。

Python代码示例： #

def backtrack_balanced(n, zeros=0, ones=0, current=''):
    if zeros + ones == n:
        yield current
        return
    if zeros < n//2:
        yield from backtrack_balanced(n, zeros+1, ones, current+'0')
    if ones < n//2:
        yield from backtrack_balanced(n, zeros, ones+1, current+'1')

# 测试n=4
for s in backtrack_balanced(4):
    print(s)

效率对比与选择建议 #

• 优先选Knuth's Algorithm L：通用场景下最优，迭代实现无栈开销，amortized O(1) per组合，代码易维护
• 类格雷码算法：适合需要相邻组合变化极小的场景，缓存友好
• 递归回溯：适合快速验证小n的需求，或者需要自定义剪枝的特殊场景

为什么这些方法比朴素方法高效？举个例子：n=30时，平衡二进制串的数量是C(30,15)=155,117,520，而所有二进制串的数量是2^30≈10亿，朴素方法要遍历10亿个串，其中80%以上都是不符合条件的，完全是浪费算力。而组合生成算法直接生成1.5亿个有效串，效率提升了近7倍，n越大提升越明显。

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