带约束的硬币找零问题：每种面额硬币最多使用两次

一、问题分析 #

你遇到的是硬币找零的排列数问题变体：给定目标金额x，硬币面额为所有不超过x的2的幂次（1,2,4,8,...），每种面额最多使用2次，求组成x的不同排列数（不同顺序算不同方案，比如1+2和2+1是两种方案）。

你的标准代码通过递归遍历所有硬币、累加子问题结果，本质是计算无使用次数限制的排列数。要加入“每种硬币最多用两次”的约束，需要在递归中跟踪每个硬币的使用次数。

二、递归解法（记忆化搜索） #

我们可以用记忆化搜索，状态包含剩余金额和每个硬币的已使用次数，确保每次选择硬币时不超过使用上限：

from functools import lru_cache

def count_coin_permutations(x):
    # 生成所有不超过x的2的幂次硬币
    coins = []
    current = 1
    while current <= x:
        coins.append(current)
        current *= 2
    coins = tuple(coins)
    coin_count = len(coins)
    
    @lru_cache(maxsize=None)
    def dp(remaining, used_counts):
        # remaining: 剩余需要凑的金额
        # used_counts: 元组，每个元素对应硬币的已使用次数（0/1/2）
        if remaining == 0:
            return 1
        if remaining < 0:
            return 0
        
        total = 0
        for idx in range(coin_count):
            if used_counts[idx] < 2:
                # 生成新的使用次数元组
                new_used = list(used_counts)
                new_used[idx] += 1
                new_used = tuple(new_used)
                # 递归处理剩余金额
                total += dp(remaining - coins[idx], new_used)
        return total
    
    # 初始状态：所有硬币使用次数为0
    initial_used = tuple([0] * coin_count)
    return dp(x, initial_used)

代码说明 #

1. 硬币生成：自动生成所有不超过目标金额x的2的幂次硬币，避免手动输入。
2. 记忆化装饰器：用lru_cache缓存已计算的状态，避免重复递归，大幅提升效率。
3. 状态跟踪：通过used_counts元组记录每个硬币的使用次数，确保每次选择硬币时不超过2次的限制。
4. 递归逻辑：遍历所有硬币，若当前硬币未达使用上限，则递归计算使用该硬币后的剩余金额方案数，累加所有可能的选择。

三、组合数解法（若需不考虑顺序的方案数） #

如果你的需求是计算组合数（不同顺序算同一种方案，比如1+2和2+1算一种），可以调整递归逻辑，按硬币面额从大到小处理，避免重复计算：

from functools import lru_cache

def count_coin_combinations(x):
    coins = []
    current = 1
    while current <= x:
        coins.append(current)
        current *= 2
    coins = tuple(coins)
    
    @lru_cache(maxsize=None)
    def dp(remaining, coin_idx):
        # remaining: 剩余金额
        # coin_idx: 当前处理的硬币索引（从后往前，避免重复组合）
        if remaining == 0:
            return 1
        if remaining < 0 or coin_idx < 0:
            return 0
        
        current_coin = coins[coin_idx]
        total = 0
        # 三种选择：不使用当前硬币、使用1次、使用2次
        total += dp(remaining, coin_idx - 1)
        if remaining >= current_coin:
            total += dp(remaining - current_coin, coin_idx - 1)
        if remaining >= 2 * current_coin:
            total += dp(remaining - 2 * current_coin, coin_idx - 1)
        return total
    
    return dp(x, len(coins)-1)

代码说明 #

1. 按索引处理：通过coin_idx限制只处理当前及之前的硬币，确保每种组合只被计算一次（比如先处理2再处理1，不会出现2+1和1+2的重复）。
2. 三种选择：对每个硬币，分别计算不使用、使用1次、使用2次的方案数，累加得到总组合数。

四、示例验证 #

• 对于x=3，排列数解法返回2（对应1+2、2+1），组合数解法返回1（对应1+2）。
• 对于x=4，排列数解法返回5（对应4、2+2、1+1+2、1+2+1、2+1+1），组合数解法返回3（对应4、2+2、1+1+2）。

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