algorithm - 找到所有组合以将一组硬币总和到一定数量

Question

我给了一个数组，我必须找到目标总和。
例如:

A[] ={1,2,3};
 S = 5;

总组合 = {1,1,1,1,1} , {2,3} , {3,2} 。 {1,1,3} , {1,3,1} , {3,1,1} 和其他可能的对

我知道这听起来像是硬币找零问题，但是问题是如何找到组合，即{2,3} 和{3,2} 是 2 种不同的解决方案。

Answer 1

在最初的硬币找零问题中，您“选择”一个任意硬币 - 并“猜测”它是否在解决方案中，这样做是因为顺序并不重要。

在这里，您必须迭代“哪个硬币是第一个”的所有可能性，直到完成:

D(0) = 1
D(x) = 0 | x < 0
D(x) = sum { D(x-coins[0]) , D(x-coins[1]), ..., D(x-coins[n-1] }

请注意，对于每一步，您都提供了选择下一个硬币并继续前进的所有可能性。最后，您总结所有的解决方案，将每个硬币放在解决方案的前面。

此解决方案的复杂性使用 DP是 O(n*S)，其中 n 是硬币的数量，S 是所需的总和。

Matlab 代码(用命令式写的，这是我目前打开的IDE，抱歉是matlab 而不是java 或C 等更常见的语言)

function [ n ] = make_change( coins, x )
    D = zeros(x,1);
    for k = 1:x
        for t = 1:length(coins)
            curr = k-coins(t);
            if curr>0
                D(k) = D(k) + D(curr);
            elseif curr == 0
                D(k) = D(k) + 1;
            end
        end
    end
    n = D(x);
end

调用将产生:

>> make_change([1,2,3],5)

ans =

    13

这是正确的，因为所有可能性都是 [1,1,1,1,1],[1,1,1,2]*4, [1,1,3]*3,[1,2, 2]*3,[2,3]*2 = 13