如何生成长度为N且连续1不超过K个的所有二进制序列？

核心思路 #

不用枚举所有2^N种可能，我们可以通过**带剪枝的回溯（本质是深度优先的动态规划）**按需构建合法字符串：

• 维护当前已构建的字符串，以及当前末尾连续1的计数
• 每一步有两种合法选择：
  1. 追加0：无论当前末尾连续1有多少，追加0后连续1计数重置为0
  2. 追加1：仅当当前末尾连续1的数量小于K时允许，追加后连续1计数加1
• 当字符串长度达到N时，将其加入结果集合

这种方法只会生成符合要求的P个字符串，完全避免了对非法字符串的计算，时间复杂度为O(P*N)（每个字符串需要N步构建），相比O(2^N)的朴素方法效率提升极大。

代码实现（Python） #

def generate_valid_binary_strings(n, k):
    result = []
    
    def backtrack(current, consecutive_ones):
        if len(current) == n:
            result.append(current)
            return
        # 追加0的分支
        backtrack(current + '0', 0)
        # 追加1的分支：仅当连续1未达上限时允许
        if consecutive_ones < k:
            backtrack(current + '1', consecutive_ones + 1)
    
    backtrack('', 0)
    return result

# 测试示例：N=4，K=2
print(generate_valid_binary_strings(4, 2))
# 输出：['0000', '0001', '0010', '0011', '0100', '0101', '1000', '1001', '1010', '1011', '1100', '1101']

与斐波那契型DP的关联 #

你提到这个问题和斐波那契问题相似，确实如此：如果仅需统计合法字符串的数量，我们可以用DP数组dp[i][j]表示长度为i、末尾有j个连续1的字符串数量，递推规则如下：

• dp[i][0] = sum(dp[i-1][0...k])：任何长度为i-1的合法字符串追加0后，末尾连续1变为0
• dp[i][j] = dp[i-1][j-1]（j从1到k）：仅当长度为i-1的字符串末尾有j-1个连续1时，才能追加1得到末尾j个连续1的字符串

但如果需要生成所有具体的字符串，上面的回溯剪枝方法更直接——它把DP的状态转移转化为实际的字符串构建过程，只走合法的状态路径，不会浪费资源在非法分支上。

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