的方式來表示的數爲K號在子集S的總和

Question

讓集合S是{1，2，4，5，10}

現在我想找到的方法來表示數數x作爲集S的K個的總和（一個號碼可以包括任何數量的次）

如果x = 10且k = 3

然後ANS應該是2 =>（5,4 ，1），（4,4,2） 數字的順序無關緊要，即（4,4,2）和（4,2,4）計爲一。

我做了一些研究，發現該集合可以表示爲多項式x^1 + x^2 + x^4 + x^5 + x^10並且在將多項式提升到冪K後，係數乘積多項式給出了ans。

但俺們包括（4,4,2）和（4,2,4）的特別條款，我不想

有沒有什麼辦法讓（4,4,2）和（4,2,4）算作同期嗎？

Answer 1

這是一個NP-complete，如所述here所述的總和子集問題的變體。

坦率地說，我不認爲你可以通過非指數（迭代通過所有組合）解決方案來解決問題，而對問題輸入沒有任何限制（如最大數量範圍等）。

對問題域沒有任何限制，我建議遍歷所有可能的k-集實例（如僞多項式時間動態規劃解決方案中所述）並查看哪些是解決方案。

檢查兩種解決方案是否相同並不比總體算法的複雜性。因此，解決方案set-elements的哈希將工作得很好：

E.g. hash-order-insensitive(4,4,2)==hash-order-insensitive(4,2,4) =>檢查整個集合，否則解決方案是不同的。 PS：你也可以逐步描述你當前的解決方案。