Partition Equal Subset Sum
分割問題を合計の半分を目標値とする0/1ナップサックとして捉え直し、boolean型のDP配列で実現可能性を判定します。
「Partition Equal Subset Sum」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
問題文
空でない正の整数配列 nums が与えられたとき、配列を合計が等しい2つの部分集合に分割できるかどうかを判定します。たとえば、[1, 5, 11, 5] は [1, 5, 5] と [11] に分割でき、どちらの合計も11になります。合計が奇数の場合、答えは直ちに False です。それ以外の場合は、合計が total_sum // 2 になる部分集合を探します。これは典型的な部分和問題です。
Subset Sum への還元
重要な還元は次のとおりです。合計 S が偶数で、ある部分集合の合計が S//2 になるなら、残りの要素の合計も自動的に S//2 になります。つまり、Partition Equal Subset Sum は、nums のいずれかの部分集合の合計が S//2 になるかどうかという問題に還元できます。これは古典的な NP 完全問題である Subset Sum であり、O(n × S) 時間の 0/1 ナップサックDPで解きます。
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False # odd sum: impossible
target = total // 2
# Now: does any subset of nums sum to target?真偽値DP配列
部分集合の合計がちょうど c になるものが存在することを、dp[c] が True であると表す真偽値配列を定義します。dp[0] = True（空集合の合計は 0）とし、それ以外はすべて False に初期化します。各数値 num について、容量を target から num まで降順に反復し（0/1 ナップサックの後ろ向き反復）、dp[c] = dp[c] or dp[c - num] を設定します。
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for c in range(target, num - 1, -1): # backward: 0/1 knapsack
dp[c] = dp[c] or dp[c - num]
return dp[target]
print(canPartition([1, 5, 11, 5])) # True
print(canPartition([1, 2, 3, 5])) # False例を追って確認する
[1, 5, 11, 5] では、total=22、target=11 です。最初は dp[0]=True です。num=1 の後は dp[1]=True になります。num=5 の後は dp[5]=True, dp[6]=True になります。num=11 の後は dp[11]=True になります（11 だけを使った場合）。すでに dp[11]=True が見つかっていますが、すべての数値の処理を続けます。最終的な答えは dp[11]=True なので、分割は可能です。
早期終了の最適化
早期終了も追加できます。途中で dp[target] が True になったら、すぐに True を返します。これにより、最良ケースを大幅に高速化できる場合があります。また、単一の要素が target と等しい場合も、すぐに True を返せます。単一の要素が target を超えている場合、その要素を target の合計になる部分集合に含めることはできませんが、残りの要素は確認する必要があります。
def canPartition_fast(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
if max(nums) > target: # any element > target makes it impossible
return False
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for c in range(target, num - 1, -1):
dp[c] = dp[c] or dp[c - num]
if dp[target]:
return True # early exit
return dp[target]
print(canPartition_fast([1, 5, 11, 5])) # TrueDP配列の代わりにPythonのSetを使う
別の方法として、到達可能な合計値の集合を保持する方法があります。{0} から開始し、各数値について、現在の集合にあるすべての合計値にその数値を加えます。reachable = reachable | {s + num for s in reachable} のように記述できます。target を超えない合計値だけを残すようにします。最後に、集合に target が含まれているかを確認します。この方法は直感的ですが、より多くのメモリを使う可能性があり、実際には遅くなる場合があります。
def canPartition_set(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
reachable = {0}
for num in nums:
reachable = {s + num for s in reachable if s + num <= target} | reachable
return target in reachable
print(canPartition_set([1, 5, 11, 5])) # True計算量の分析
DPによる方法は、S = sum(nums) としたとき、O(n × S) 時間で実行され、真偽値配列のためにO(S) 空間を使用します。LeetCodeの制約（n ≤ 200、sum ≤ 20,000）では、最大でも 4,000,000 回の操作であり、非常に高速です。集合を使う方法も漸近的な計算量は同じですが、集合の構築コストのため、実際には遅くなる可能性があります。
一般化：合計が一致する部分集合を数える
関連する問題として、合計が target になる部分集合の数を数える問題があります。DPを真偽値から整数に変更し、dp[c] = number of ways to reach sum c とします。OR の代わりに加算を使い、dp[c] += dp[c - num] とします。dp[0] = 1 で初期化し、同じように後ろ向きに反復します。この一般化から、部分集合に関するさまざまな問いに合わせてナップサックのテンプレートを応用できることがわかります。
def count_subsets(nums, target):
dp = [0] * (target + 1)
dp[0] = 1
for num in nums:
for c in range(target, num - 1, -1):
dp[c] += dp[c - num]
return dp[target]
print(count_subsets([1, 1, 1, 1, 1], 3)) # 10 (C(5,3))面接でよくある追加質問
次のような追加質問が予想されます。(1) 実際の分割結果を返す必要がある場合はどうしますか？ — 復元のために2次元DPが必要です。(2) 要素が負数になる可能性がある場合はどうしますか？ — target をずらすか、配列の代わりに辞書を使います。(3) 時間計算量はいくつですか？ — O(n × sum) です。(4) 同じ数値が多数ある場合に改善できますか？ — できます。頻度を数えることで、外側の反復回数を減らせます。こうしたトレードオフは、先回りして必ず説明しましょう。
0/1ナップサックとの関連
Partition Equal Subset Sum は、0/1ナップサックを直接応用したものです。アイテムが数値に対応し、重みと価値は等しく、ナップサックの容量は target に相当します。最大価値がいくつになるかではなく、最大価値が target と等しくなるかどうか（実現可能性）を調べます。後ろ向きの反復は同じで、演算だけが max から真偽値の or に変わります。面接でこの関連性を見抜けると、優れたパターン認識力を示せます。
エッジケース
対処すべきエッジケースは次のとおりです。(1) 長さ1の配列 — 1つの要素を分割することはできないため、常に False です。(2) すべての要素が同じで個数が偶数 — 個々の値によって、うまくいく場合といかない場合があります。(3) 合計が非常に大きい場合 — DP配列を確保する前に制約を確認します。(4) target より大きい要素 — target になる部分集合の一部にはなれないため、スキップできます。最大要素を確認して早期終了することで、ケース (4) を効率よく処理できます。
理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、Partition Equal Subset Sum は target = total//2 の部分和問題に還元できること、真偽値1次元DPの dp[c] は 0/1ナップサックと同じ後ろ向きの反復を使うこと、そして真偽値の OR を整数の加算に置き換えることで、部分集合の個数を数える問題に一般化できることを学びました。次は Target Sum に取り組み、符号の割り当てを部分和の差に関するナップサック問題へ変換します。
よくある質問
「Partition Equal Subset Sum」レッスンは無料ですか？
はい。「Partition Equal Subset Sum」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「Partition Equal Subset Sum」で何を学びますか？
分割問題を合計の半分を目標値とする0/1ナップサックとして捉え直し、boolean型のDP配列で実現可能性を判定します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「Partition Equal Subset Sum」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 0/1ナップサックと空間最適化
- 非有界ナップサックとCoin Change II
- Partition Equal Subset Sum
- 正負の符号を使うTarget Sum