无法理解《Python数据结构与算法思维》中的n位二进制字符串生成回溯问题

题目核心要求 #

生成所有长度恰好为n的二进制字符串，每个字符串仅由0和1组成。比如n=2时，结果应为["00","01","10","11"]，总共有2ⁿ个这样的字符串（对应n位二进制数的所有可能组合）。

原代码的错误分析 #

书中给出的代码存在逻辑错误，导致运行结果不符合“n位”的要求：

def appendAtFront(x,L):
    return [x+element for element in L]
def bitStrings(n):
    if n == 0: return []
    if n == 1: return ["0", "1"]
    else:
        # 此处逻辑错误：错误地将n-1位字符串与"1"+n-1位字符串拼接后，再统一加"0"
        return (appendAtFront("0", bitStrings(n-1) + appendAtFront("1", bitStrings(n-1))))

这个错误会导致生成的字符串长度混乱，比如n=4时出现"00010"这类长度为5的字符串，完全偏离了题目要求。

修正后的正确代码 #

正确逻辑是：所有n位二进制字符串 = （每个n-1位字符串前加"0"） + （每个n-1位字符串前加"1"）。修正后的代码如下：

def appendAtFront(x, L):
    return [x + element for element in L]

def bitStrings(n):
    if n == 0:
        return []
    if n == 1:
        return ["0", "1"]
    else:
        # 拆分逻辑：分别生成以0和1开头的n位字符串，再合并
        start_with_0 = appendAtFront("0", bitStrings(n-1))
        start_with_1 = appendAtFront("1", bitStrings(n-1))
        return start_with_0 + start_with_1

print(bitStrings(4))

代码逻辑解释 #

• 基础情况：当n=1时，直接返回最基本的两个1位二进制字符串["0","1"]；当n=0时返回空列表。
• 递归逻辑：对于n>1的情况，先递归获取所有长度为n-1的二进制字符串，然后分别给每个字符串前缀添加"0"和"1"，最后将这两组结果合并，得到所有长度为n的二进制字符串。

运行修正后的代码，n=4的输出为符合要求的16个4位二进制字符串：

['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']

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