如何用Python递归实现鸡块数拆分，获取所有组合方案

你现在要解决的是用6、9、20块装的鸡块包，凑出1-65块的所有可能组合，且要求用递归实现——原来的循环代码因为找到第一个符合条件的组合就return，所以只能输出一种方案，再加上递归逻辑嵌套在循环里，整体结构也有问题。

递归核心思路 #

递归的关键是逐步拆解目标数量：每次选定一种包装的使用数量，然后递归处理剩余的数量，直到剩余数量为0（找到有效组合）或者小于0（无效路径）。为了避免重复枚举相同组合（比如先拿1个6再拿1个9，和先拿1个9再拿1个6，本质是同一种组合），我们固定包装的选择顺序（比如从大到小：20→9→6），确保每个组合只被遍历一次。

完整递归代码实现 #

def find_combinations(remaining, current_counts, pack_index):
    # 定义包装规格，按从大到小排列以减少递归次数
    packs = [20, 9, 6]
    
    # 基准情况1：剩余数量为0，找到有效组合，输出结果
    if remaining == 0:
        total = 6*current_counts[6] + 9*current_counts[9] + 20*current_counts[20]
        print(f"For {total} total;")
        print(f"6 piece can be {current_counts[6]}")
        print(f"9 piece can be {current_counts[9]}")
        print(f"20 piece can be {current_counts[20]}")
        print("---")
        return
    
    # 基准情况2：剩余数量不足，或无更多包装可选，终止当前递归分支
    if remaining < 0 or pack_index >= len(packs):
        return
    
    current_pack = packs[pack_index]
    # 枚举当前包装的所有可能使用数量：从0到最多能拿的个数
    max_count = remaining // current_pack
    for count in range(0, max_count + 1):
        # 复制当前组合，避免修改原字典影响后续递归分支
        new_counts = current_counts.copy()
        new_counts[current_pack] = count
        # 递归处理剩余数量，同时切换到下一个包装（固定顺序避免重复组合）
        find_combinations(remaining - count * current_pack, new_counts, pack_index + 1)

# 遍历1到65的所有目标鸡块数，查找每个数的全组合
for x in range(1, 66):
    print(f"\n=== 查找{x}块的所有组合 ===")
    # 初始化各包装数量为0
    initial_counts = {6: 0, 9: 0, 20: 0}
    find_combinations(x, initial_counts, 0)

代码细节说明 #

1. 基准条件：
   • 当remaining（剩余需要凑的数量）为0时，说明当前组合有效，直接输出结果。
   • 当remaining小于0，或者已经遍历完所有包装时，终止当前递归分支，避免无效计算。
2. 递归过程：
   • 对当前选定的包装，枚举所有可能的使用数量（从0到remaining // current_pack）。
   • 每次枚举后复制当前组合字典，更新对应包装的数量，再递归处理剩余数量并切换到下一个包装——这样保证了组合的唯一性，不会出现顺序不同但数量相同的重复结果。
3. 调用逻辑：
   • 遍历1到65的每个目标数量，初始化组合后调用递归函数，确保每个数的所有有效组合都被输出。

原代码的问题点 #

原代码在找到第一个符合条件的组合后就return，还嵌套调用了testtheorem(x+1)，导致每个数量只输出一种方案，同时打乱了循环的正常逻辑。而上面的递归代码会完整遍历所有可能的组合路径，确保每个数量的所有有效组合都被输出。

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