arrays - 与えられた合計で K 個の要素の部分列を見つける

Question

重複の可能性:
固定サブセット サイズの合計サブセット

Aだから私は要素を持つ配列を持っていますA[1], A[2] .. A[N]

正確に要素を持ちK、合計が正確Sumに

K 個のネストされたループを実行し、すべての可能性をテストする場合、私の最善の推測は O(N ^{K ) です。}

これはより速く行うことができますか？

のすべての要素はA、0 より大きい整数です。

Answer 1

これは多項式時間では解決できないと思います。@アンダーソンは正しいです。それはナップザックの問題に似ています。

分岐限定アルゴリズムで高速化できますが、その効果は実際の値に基づいています。(例: 合計を超えた場合は、それ以上テストしないでください)

編集: @amitがリンクしたトピックに基づいて、O(n^k)は確かに最良の答えであり、固定されたk値に対してnの多項式です。