我正在尝试实现硬币问题，问题说明如下
创建一个函数来计算可用于给定数量的硬币的所有可能组合。
All possible combinations for given amount=15, coin types=1 6 7 1) 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 2) 1,1,1,1,1,1,1,1,1,6, 3) 1,1,1,1,1,1,1,1,7, 4) 1,1,1,6,6, 5) 1,1,6,7, 6) 1,7,7,
功能原型：
int findCombinationsCount(int amount, int coins[])
假设硬币阵列已排序。对于上面的示例，此函数应返回6。
有人指导我如何实现这一目标吗？
您可以使用生成函数方法来给出使用复数的快速算法。
给定硬币值c1，c2，..，ck，以获得求和n的方法数量，您需要的是x的系数
(1 + x^c1 + x^(2c1) + x^(3c1) + ...)(1+x^c2 + x^(2c2) + x^(3c2) + ...)....(1+x^ck + x^(2ck) + x^(3ck) + ...)
这与在中找到x ^ n的系数相同
1/(1-x^c1) * 1/(1-x^c2) * ... * (1-x^ck)
现在使用复数，x ^ a-1 =（x-w1）（x-w2）…（x-wa）其中w1，w2等是单位的复数根。
所以
可以写成
1/(x-a1)(x-a2)....(x-am)
可以使用部分分数重写的是
A1/(x-a1) + A2/(x-a2) + ... + Am/(x-am)
可以很容易地找到x ^ n的系数：
A1/(a1)^(n+1) + A2/(a2)^(n+1) + ...+ Am/(am)^(n+1).
计算机程序应该很容易就能找到Ai和ai（可能是复数）。当然，这可能涉及浮点计算。
对于较大的n，这可能比枚举所有可能的组合要快。
希望有帮助。
