如何使用Python递归打印包含相等数量a、b的所有排列字符串

现有代码问题 #

• 未限制a和b的使用数量，会生成所有长度等于输入值的a/b组合，而非a、b各占一半的目标结果
• 初始调用时current传入了空格，会导致输出结果开头多一个多余空白字符
• 函数本身无返回值，外层调用的print()会额外输出None

调整思路 #

• 先校验输入长度是否为偶数，奇数长度不可能存在a、b数量相等的字符串，直接给出提示
• 递归过程中跟踪剩余可使用的a、b数量，仅当对应字符剩余量大于0时，才拼接该字符进入下一层递归
• 移除多余的初始空格和外层无效print
• 当a、b剩余量均为0时，打印当前拼接完成的字符串

调整后代码 #

def ab_equal(length):
    # 校验输入合法性
    if length % 2 != 0:
        print("输入长度需为偶数")
        return
    # a、b各需要的数量
    count = length // 2
    # 递归回溯函数
    def backtrack(remain_a, remain_b, current):
        # 两个字符都已用完，打印结果
        if remain_a == 0 and remain_b == 0:
            print(current)
            return
        # 还有剩余a可以使用时，拼接a进入下一层
        if remain_a > 0:
            backtrack(remain_a - 1, remain_b, current + "a")
        # 还有剩余b可以使用时，拼接b进入下一层
        if remain_b > 0:
            backtrack(remain_a, remain_b - 1, current + "b")
    backtrack(count, count, "")

if __name__ == "__main__":
    ab_equal(4)

运行效果 #

输入4时输出结果为：

aabb
abab
abba
baab
baba
bbaa

完全匹配需求示例。

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