生成所有可能的二进制字符串

题目

生成所有可能的二进制字符串

信息

• 类型：问答
• 难度：⭐

考点

回溯算法,递归实现,字符串处理

快速回答

使用回溯算法生成所有长度为 n 的二进制字符串（仅包含 '0' 和 '1'）。核心步骤如下：

• 从空字符串开始构建，每次添加 '0' 或 '1'
• 当字符串长度等于 n 时，保存结果
• 递归探索所有可能的选择路径
• 无需显式回溯（字符串不可变）

时间复杂度：O(2ⁿ)，空间复杂度：O(n)（递归深度）

解析

问题描述

给定一个整数 n，生成所有长度为 n 的二进制字符串（仅由字符 '0' 和 '1' 组成）。例如：

• 输入：n=2
• 输出：['00','01','10','11']

原理说明

回溯算法通过递归尝试所有可能的选择：

1. 从空字符串开始构建
2. 在每一步决策中，添加 '0' 或 '1'
3. 当字符串长度达到 n 时，将结果加入列表
4. 递归过程自动处理路径探索和状态回退

由于字符串在 Python 中是不可变对象，每次递归调用会创建新字符串，因此不需要显式的撤销操作（这与使用可变列表不同）。

代码示例（Python）

def generate_binary_strings(n):
    def backtrack(current):
        # 终止条件：当前字符串长度等于 n
        if len(current) == n:
            result.append(current)
            return

        # 尝试两种选择：添加 '0' 或 '1'
        backtrack(current + '0')
        backtrack(current + '1')

    result = []
    backtrack('')
    return result

# 测试
print(generate_binary_strings(2))  # 输出：['00', '01', '10', '11']

最佳实践

• 递归终止条件：明确当字符串长度等于 n 时保存结果
• 避免可变状态：直接传递新字符串（current + '0'）而非修改共享变量
• 结果存储：使用闭包变量（result）收集结果，避免全局变量
• 剪枝优化：本题无无效路径，无需剪枝（若需限制如“不能连续1”，可添加条件判断）

常见错误

• 忘记终止条件：导致无限递归和栈溢出
• 修改共享状态：错误地使用可变列表而未回溯（如用 list.append() 后未 pop()）
• 错误传递状态：在递归调用后错误地修改 current 变量（应直接传递新值）
• 顺序问题：先添加 '0' 或 '1' 会影响结果顺序，但题目通常不要求特定顺序

扩展知识

• 时间复杂度：O(2ⁿ)，每个位置有 2 种选择，共 n 层递归
• 空间复杂度：O(n) 递归调用栈深度，结果存储 O(n·2ⁿ)
• 迭代替代方案：可用位运算生成（如遍历 0 到 2ⁿ-1 的二进制表示）
• 变体问题：
  • 生成 k 进制字符串（0 到 k-1）
  • 添加约束条件（如禁止连续两个 '1'）
  • 生成组合而非排列（如子集问题）