Python递归生成字符串全排列中char_count[i] +=1的作用是什么？

你提到的这段代码是用回溯法生成输入字符串的所有全排列，其中char_count数组用来统计每个小写字母在原字符串中的出现次数。

核心逻辑拆解 #

在递归函数search里，这段代码的流程是：

if char_count[i] > 0:
    char_count[i] -= 1
    search(curr + chr(ord("a") + i))
    char_count[i] += 1

• char_count[i] -= 1：当选中第i个字母加入当前排列curr时，把该字母的剩余可用次数减1，标记它已经被用了一次，避免在后续递归分支里重复使用超出原字符串的数量。
• 递归调用search(...)：进入下一层递归，继续构建剩余长度的排列。
• char_count[i] += 1的作用：这是回溯法里的「现场恢复」操作。当以当前字母开头的所有排列都生成完毕（递归调用返回），需要把该字母的可用次数加回去，让它可以被上层递归的其他循环分支使用。

举个简单例子：如果输入是"aab"，第一次循环选中第一个'a'（char_count[0]从2减到1），递归生成所有以这个'a'开头的排列（"aab"、"aba"）。等这部分递归全部完成返回后，执行char_count[0] +=1把计数恢复回2，这样后续循环选中第二个'a'时，才能正常生成"baa"这个排列。如果没有这一步，char_count[0]会一直是1，后续分支就无法正确使用第二个'a'了。

完整代码回顾 #

s = input()
perms = []
char_count = [0] * 26


def search(curr: str = ""):
    # 生成完一个完整排列，加入结果列表
    if len(curr) == len(s):
        perms.append(curr)
        return
    for i in range(26):
        # 只处理还有剩余可用次数的字符
        if char_count[i] > 0:
            # 标记该字符已使用一次
            char_count[i] -= 1
            # 递归构建后续排列
            search(curr + chr(ord("a") + i))
            # 恢复字符可用次数，供其他分支使用
            char_count[i] += 1


# 初始化字符计数
for c in s:
    char_count[ord(c) - ord("a")] += 1

search()

# 输出结果
print(len(perms))
for perm in perms:
    print(perm)

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