python - 查找整数的线性组合

Question

我试过了，但找不到类似的问题。如果有重复的问题，请给我链接。

我在论坛上看到有人问一个有趣的算法问题。问题是将 106 分成 10、20、50、1、2 和 5 的线性组合有多少种方法？例如，106=10*6+1*6，106=50*2+2*1+1*4。

我用python解决了这个问题，但是 super 慢。我还概括了我的函数，因此它不仅可以应用于 106，还可以应用于其他数字。

有什么方法可以让我的算法更快？我需要几分钟才能找到 160 种方法，这在所有解决方案中只是很小的一部分，而且我没有耐心等待更多结果，因为随着递归的进行，一个解决方案将花费越来越多的时间。

def main(total,*args):
    def recursion(Sum,method):          
        for arg in args:
            if Sum<arg:
                continue
            method[arg]+=1
            if Sum>arg:
                recursion(Sum-arg,method)
            else:
                methods.append(method.copy())
            method[arg]-=1
    methods=[]
    recursion(total,{ arg:0 for arg in args})
    return len(methods)

main(106,10,20,50,1,2,5)

Answer 1

这类似于硬币找零问题。您可以引用以下链接了解各种解决方案: coin change problem gfg