Python实现二十一点所有≥17点可能手牌的递归算法问题求解

问题根因 #

你的递归逻辑缺少回溯时的状态恢复操作，存在3个核心错误：

1. 遍历deck的同时直接修改原deck执行remove操作，会导致遍历索引错位，跳过大量牌的遍历
2. 递归返回后没有恢复deck的原始状态，上层循环的deck已经被下层递归改空，无法走其他分支
3. 进入else分支递归返回后，没有删除当前加入runningList的牌，导致手牌残留多余元素

修正后的实现 #

def simPlayerHelper(deck, runningList, playerPossibilities):
    current_sum = sum(runningList)
    # 按索引遍历避免遍历过程中deck变动导致的错位
    for i in range(len(deck)):
        card = deck[i]
        runningList.append(card)
        new_sum = current_sum + card
        if new_sum >= 17:
            playerPossibilities.append(runningList.copy())
        else:
            # 构造移除当前牌的新deck传入下层，不修改原deck
            new_deck = deck[:i] + deck[i+1:]
            simPlayerHelper(new_deck, runningList, playerPossibilities)
        # 回溯：恢复手牌状态
        runningList.pop()

# 调用示例
if __name__ == "__main__":
    test_deck = [2,2,2,2,3,3,3,3,4,4,4,4]
    test_running = [10,2]
    result = []
    simPlayerHelper(test_deck, test_running, result)
    for valid_hand in result:
        print(valid_hand)

关键逻辑说明 #

• 所有递归分支都不会修改传入的原始deck，每次下钻都构造新的剩余牌组，保证上层遍历可以覆盖所有牌的分支
• 每个牌的分支处理完成后，统一用pop()删除当前加入手牌的牌，恢复手牌的初始状态，确保下一轮循环的手牌状态正确
• 提前计算当前手牌总和，避免重复sum计算，性能更优

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