awesomoの答えに基づいて構築するには...数値がソートされていると仮定できる場合、特定のkに対してO（n ^ k）よりもうまくいくことができます。サイズ (k-1) のすべての O(n^(k-1)) サブセットを取得し、最初の (k-1) に追加されたときに残りの数値をバイナリ検索します。これは O(n^(k-1) log n) です。これは、複雑さが確かにそれよりも少ないことを意味します。
実際、複雑さが k=3 の場合に O(n^2) であることがわかっている場合、k > 3 の場合はさらに適切に処理できます: O(n^( k-3))、残りの要素で O(n^2) の問題を解きます。これは、k >= 3 の場合、O(n^(k-1)) です。
しかし、おそらくあなたはもっとうまくやれるでしょうか？これについて考えてみます。
編集: 最初は、この問題に対する別の見方を提案する多くのことを追加するつもりでしたが、要約版を投稿することにしました。他の投稿者には、このアイデアにメリットがあるかどうかを確認することをお勧めします。分析は難しいですが、機能するのに十分クレイジーかもしれません。
k が固定されているという事実と、奇数と偶数の合計が特定の方法で動作するという事実を使用して、この問題を解決するための再帰アルゴリズムを定義できます。
最初に、リストに偶数と奇数の両方が含まれるように問題を修正します (これは、すべてが偶数の場合は 2 で割るか、すべてが奇数の場合は数値から 1 を引き、目標の合計から k を引き、繰り返します。必要に応じて）。
次に、奇数の偶数を使用することによってのみ目標合計が偶数に達することができ、奇数の奇数の奇数のみを使用することによってのみ目標合計が奇数に達することができるという事実を使用します。適切な奇数のサブセットを生成し、偶数、合計から検査対象の奇数のサブセットの合計を引いたもの、および k から奇数のサブセットのサイズを引いたものを使用して、再帰的にアルゴリズムを呼び出します。k = 1 の場合、二分探索を行います。k > n の場合 (これが起こるかどうかはわかりません)、false を返します。
奇数が非常に少ない場合、これにより、勝者のサブセットの一部である必要がある用語を非常に迅速に選択したり、そうでないものを破棄したりできます。引き算のトリックを使用して、偶数が多い問題を奇数が多い同等の問題に変換できます。したがって、最悪のケースは、偶数と奇数の数が非常に似ている場合に違いありません...そしてそれが私が今いる場所です. これに対する無駄に緩い上限は、ブルートフォースよりも何桁も悪いですが、少なくともブルートフォースと同じくらい良いと思います. 考えは大歓迎です！
EDIT2：説明のための上記の例。
{1, 2, 2, 6, 7, 7, 20}, k = 3, sum = 20.
Subset {}:
{2, 2, 6, 20}, k = 3, sum = 20
= {1, 1, 3, 10}, k = 3, sum = 10
Subset {}:
{10}, k = 3, sum = 10
Failure
Subset {1, 1}:
{10}, k = 1, sum = 8
Failure
Subset {1, 3}:
{10}, k = 1, sum = 6
Failure
Subset {1, 7}:
{2, 2, 6, 20}, k = 1, sum = 12
Failure
Subset {7, 7}:
{2, 2, 6, 20}, k = 1, sum = 6
Success