Partition Equal Subset Sum

合計から始めます。合計が奇数なら、2つの等しい整数の和は偶数になるため、分割は存在しません。それ以外の場合、各グループの合計はちょうど target = total / 2 になる必要があります。target になる値を見つけたら、選ばなかった値だけで、もう半分ができます。つまり、1つの問いだけで十分です。ある部分集合の合計が target になるでしょうか？

値を順に見て、それぞれについて、最初のグループに入れるか、2番目のグループ用に残すかを選びます。補助関数 reach(i, remaining) は、インデックス i 以降の値で remaining を作れるかどうかを判定します。remaining が 0 になったら true を返し、値が尽きるか 0 未満になったら false を返します。それ以外の場合は、nums[i] を使う選択と使わない選択の両方を試します。

すべての部分集合は選択の経路の1つなので、この探索で分割を見落とすことはなく、答えは正確です。ただし、経路が 2^n 個あるため遅く、分割できない入力では、そのほとんどすべてを試すことになります。100を199個と98を1個用意した場合を考えてください。合計は19998で、目標の9999には決して到達しません。探索では、100を高々99個選ぶすべての方法を試すことになり、その数は約 4 × 10^59 経路です。値が40個だけでも 2^40、約 10^12 経路になります。

再帰は同じ質問を何度も繰り返します。reach(i, remaining) は2つの数値だけに依存します。i は0からnまで、remaining は0からtargetまでです。そのため、異なる質問は最大でも (n+1) × (target+1) 個です。上限では約 201 × 10001 ≈ 2 × 10^6 個となり、すべてに一度ずつ答えるには十分少ない数です。

表を使って答えを順に構築します。can[i][s] は、最初のi個の値のうちいくつかを足してsになるかどうかを表します。値がない場合、可能なのは合計0だけなので、行0ではcan[0][0]を除いてすべてfalseです。値num = nums[i-1]を使ってsに到達する方法は2つあります。numを使わず、前の値だけですでにsに到達している場合か、numを使い、前の値でs-numに到達している場合です。これがすべての規則です。can[i][s] = can[i-1][s] or can[i-1][s-num] ただし、2つ目の条件が当てはまるのはs ≥ numの場合だけです。各行は直前の行だけを参照するので、それぞれの値は最大1回しか使われません。

targetが11の[6, 1, 4, 9, 2]では、到達可能な合計は{0}から{0, 6}へ、次に{0, 1, 6, 7}へ、そして{0, 1, 4, 5, 6, 7, 10, 11}へと増えていきます。合計11は4を加えた後（6 + 1 + 4）に現れ、その後の行にも残ります。答えはcan[n][target]です。各セルの計算は定数時間なので、時間計算量とメモリ計算量はどちらも O(n × target) です。

表の各行はその1つ上の行だけを参照するため、値をその場で更新するなら1行あれば十分です。reach[s] は、これまでに見た値の一部の合計が s になるかどうかを示します。注意すべきなのは更新の順序です。s を小さい方から大きい方へ走査すると、同じ num によって reach[s-num] がすでに true になっている可能性があります。[3, 9] と目標値 6 の場合、3によって reach[3] が true になり、続いてそこを参照して reach[6] も true にしてしまいます。まるで3を2つ持っているかのように扱われ、存在しない分割に対して true と答えてしまいます。

s を target から num まで、小さい方へ向かって走査しましょう。すると s-num はより小さいインデックスであり、この値によってまだ変更されていません。そのため、reach[s-num] には num が加わる前の答えが保持されています。これは表の can[i-1][s-num] とまったく同じで、1行だけで表全体と同じ処理ができます。

reach[target] が true になった時点で処理を止めることもできます。後から来る値は到達可能な合計を増やすだけで、取り消すことはないからです。最悪の場合でも O(n × target) 回、約 2 × 10^6 回の処理が必要で、メモリ使用量は target + 1 個のブール値に減ります。