總和組合列表

Question

我需要一個算法來解決這個問題：

給定一組n個自然數x1，x2，...，xn，數字S和k。形成從集合中挑選的k個數字的總和（一個數字可以選擇多次），總和爲S.

換句話說：列出S的所有可能的組合：邊界：n < = 256，x < = 1000，k < = 32

例如

problem instance: {1,2,5,9,11,12,14,15}, S=30, k=3 
    There are 4 possible combinations 
    S=1+14+15, 2+14+14, 5+11+15, 9+9+12. 

有了這些界限，使用暴力是不可行的，但我認爲動態規劃是一種好方法。該方案是：表t，其中t [m，v] =由m個數形成的總和v的組合數。

1. Initialize t[1,x(i)], for every i. 
2. Then use formula t[m,v]=Sum(t[m-1,v-x(i)], every i satisfied v-x(i)>0), 2<=m<=k. 
3. After obtaining t[k,S], I can trace back to find all the combinations. 

的困境是，T [M，V]可通過重複的可交換的組合增加例如，T [2,16] = 2由於16 = 15 + 1和1 + 15。此外，由於1 + 14 + 15,1 + 15 + 14，...，2 + 14 + 14,14 + 2 + 14，最終結果f [3,30]很大，...

如何擺脫對稱排列？提前致謝。

Answer 1

您可以通過在選擇x的元素的方式上施加排序來擺脫排列。使你的表三重t[m, v, n] =總數v組成的組合數m數字從x1..xn。現在觀察t[m, v, n] = t[m, v, n-1] + t[m-1, v-x_n, n]。這解決了排列問題，只通過從x中的外觀開始以相反的順序生成加數。因此，例如它會生成15 + 14 + 1和14 + 14 + 2，但從來沒有14 + 15 + 1。

（你可能不需要填寫完整的表，所以你應該計算懶洋洋地;實際上，一個memoized遞歸函數可能是你想要的這裏）