部分和問題を解くための新しいアルゴリズムを思いついたのですが、それは多項式時間だと思います。私が間違っているか、天才だと言ってください。
クイックスターターファクト：
部分和問題はNP完全問題です。多項式時間でそれを解くことは、P=NPを意味します。
長さNのセット内のサブセットの数は2^Nです。
より有用な一方で、長さNの一意のサブセットの数は、最大でセット全体の合計から最小の要素を引いたものです。または、サブセットが生成できる可能性のある合計の範囲は、すべての負の要素の合計の間にあります。そして、すべての正の要素の合計。これは、すべての正または負の合計よりも大きいまたは小さい合計はあり得ないためです。これらの合計は、要素を追加すると線形速度で増加します。
これが意味するのは、Nが増加すると、重複するサブセットの数が指数関数的に増加し、一意で有用なサブセットの数が直線的にのみ増加することです。可能な限り早い機会に重複サブセットを削除できるアルゴリズムを考案できれば、多項式時間で実行できます。簡単な例は、バイナリから簡単に取得できます。2の累乗である数値のみから、任意の整数値に対して一意のサブセットを作成できます。そのため、他の数を含むサブセット（2の累乗がすべてある場合）は重複していて無駄です。それらとその導関数を計算しないことにより、2の累乗である数値が任意の整数と比較して対数的に発生するため、アルゴリズムの実行時間を実質的にすべて節約できます。
そのため、これらの重複を削除し、それらとそのすべての導関数を計算する必要をなくす単純なアルゴリズムを提案します。
まず、O（N log N）のみのセットを並べ替え、正と負の2つに分割します。負の数の手順は同じなので、正の数の概要のみを説明します（明確にするために、セットは正の半分だけを意味します）。
sumでインデックス付けされた配列を想像してみてください。この配列には、正の側のすべての可能な結果の合計のエントリがあります（線形のみです。覚えておいてください）。エントリを追加すると、値はサブセット内のエントリになります。したがって、array [3] = {1、2}のようになります。
一般に、セット内のすべてのサブセットを列挙するように移動します。これを行うには、1つの長さのサブセットから始めて、それらに追加します。すべての一意のサブセットがある場合、それらは配列を形成し、Horowitz/Sahniで使用されている方法でそれらを単純に反復します。
ここで、「第1世代」の値から始めます。つまり、元のデータセットに重複する数値がなかった場合、これらの値に重複がないことが保証されます。つまり、すべての単一値サブセット、およびセットのすべての長さから1つの長さのサブセットを引いたものです。これらは、セットを合計し、各要素を順番に減算することで簡単に生成できます。さらに、セット自体は、有効な第1世代の合計とサブセット、およびサブセットの個々の要素です。
次に、第2世代の値を実行します。配列内の各値をループし、一意のサブセットごとに、値がない場合はそれを追加して、新しい一意のサブセットを計算します。重複していると、楽しいことが起こります。衝突リストに追加します。新しいサブセットを追加するときは、それらが衝突リストにあるかどうかを確認します。あまり望ましくない（通常は大きいが、任意である可能性がある）等しいサブセットによってキーを設定します。サブセットに追加する場合、衝突が発生したとしても、何もしません。より望ましいサブセットを追加する場合、チェックを見逃して追加し、共通のサブセットを生成します。その後、他の世代のために繰り返します。
この方法で重複サブセットを削除することにより、重複をセットの残りの部分と結合し続ける必要も、衝突をチェックし続ける必要も、合計する必要もありません。最も重要なことは、一意ではない新しいサブセットを作成しないことで、それらから新しいサブセットを生成しないことです。これにより、アルゴリズムがNPからPに変わる可能性があります。これは、サブセットの成長が指数関数的ではなくなったためです。破棄します。それらの大部分は、次世代で「複製」し、他の重複しないサブセットと組み合わせることによって、より多くのサブセットを作成する前に行われます。
私はこれをあまりよく説明していないと思います。私は写真を持っています...それらは私の頭の中にあります。重要なことは、重複するサブセットを破棄することで、実質的にすべての複雑さを取り除くことができるということです。
たとえば、（この例を手作業で行っているため）ゼロを目指す-7から7（ゼロではない）の単純なデータセットを想像してみてください。並べ替えて分割すると、（1、2、3、4、5、6、7）が残ります。合計は28です。ただし、2 ^ 7は128です。したがって、128個のサブセットが1 .. 28の範囲に収まります。つまり、100セットが重複していることが事前にわかっています。8の場合、スロットは36しかありませんが、サブセットは256になります。したがって、重複の数が以前の2倍を超える220になっていることが簡単にわかります。
この場合、第1世代の値は1、2、3、4、5、6、7、28、27、26、25、24、23、22、21であり、それらを構成コンポーネントにマップします。
1 = { 1 }
2 = { 2 }
...
28 = { 1, 2, 3, 4, 5, 6, 7 }
27 = { 2, 3, 4, 5, 6, 7 }
26 = { 1, 3, 4, 5, 6, 7 }
...
21 = { 1, 2, 3, 4, 5, 6 }
ここで、新しいサブセットを生成するために、各サブセットを順番に取得し、相互サブセットがない限り、他のサブセットに追加します。たとえば、28と27にはhueg相互サブセットがあります。したがって、1を取得して2に追加すると、3 = {1、2}になりますが、お待ちください。すでにアレイに含まれています。これが意味するのは、すでに2が含まれているサブセットに1を追加しないこと、およびその逆のことです。これは、3のサブセットと重複しているためです。
今、私たちは持っています
1 = { 1 }
2 = { 2 }
// Didn't add 1 to 2 to get 3 because that's a dupe
3 = { 3 } // Add 1 to 3, amagad, get a duplicate. Repeat the process.
4 = { 4 } // And again.
...
8 = { 1, 7 }
21? Already has 1 in.
...
27? We already have 28
ここで、すべてに2を追加します。
1? Existing duplicate
3? Get a new duplicate
...
9 = { 2, 7 }
10 = { 1, 2, 7 }
21? Already has 2 in
...
26? Already have 28
27? Got 2 in already.
3？
1? Existing dupe
2? Existing dupe
4? New duplicate
5? New duplicate
6? New duplicate
7? New duplicate
11 = { 1, 3, 7 }
12 = { 2, 3, 7 }
13 = { 1, 2, 3, 7 }
ご覧のとおり、毎回新しいサブセットを追加していますが、量は直線的にしか増加していません。
4？
1? Existing dupe
2? Existing dupe
3? Existing dupe
5? New duplicate
6? New duplicate
7? New duplicate
8? New duplicate
9? New duplicate
14 = {1, 2, 4, 7}
15 = {1, 3, 4, 7}
16 = {2, 3, 4, 7}
17 = {1, 2, 3, 4, 7}
5？
1,2,3,4 existing duplicate
6,7,8,9,10,11,12 new duplicate
18 = {1, 2, 3, 5, 7}
19 = {1, 2, 4, 5, 7}
20 = {1, 3, 4, 5, 7}
21 = new duplicate
これで範囲内のすべての値が得られたので、停止してリスト1-28に追加します。負の数について繰り返し、リストを繰り返します。
編集：
このアルゴリズムは、どのような場合でも完全に間違っています。合計が重複しているサブセットは、到達方法が異なるため、つまり、折りたたむことができないため、サブセットを生成できる目的で重複することはありません。