找到K個元素的子給定的總和

Question

可能重複：
Sum-subset with a fixed subset size

所以我有一個數組A，包含元素A[1], A[2] .. A[N]

我想找到一個子（不一定是連續的），具有K元素，其總和恰好爲Sum。

我最好的估計是O（N ^K），如果你運行K嵌套循環，並測試每一種可能性。

這可以做得更快嗎？

的A所有的元素都是整數，大於0

Answer 1

我覺得這不能polinomial及時解決。 @安德森是對的，它確實像揹包問題。

儘管您可以通過branch and bound算法使其更快，但它的有效性將基於您的實際值。 （例如：如果你超過總和，不進一步測試）

編輯： 基礎上的話題，什麼@amit聯繫，爲O（n^k）是確實是最好的答案，這是polinomial在n，任何固定的k值。