C++で配列を等しい和の2つの部分集合に分割できるか判定する方法

問題概要

正の整数のみを含む空でない配列が与えられたとき、その配列を要素の合計が等しい2つの部分集合に分割できるかどうかを判定します。

例えば、入力が [1, 5, 11, 5] の場合、出力は true になります。これは、この配列を [1, 5, 5] と [11] の2つの部分集合に分けると、どちらも合計が 11 で等しくなるためです。

解法のアプローチ(動的計画法)

この問題は「部分和問題」の一種であり、動的計画法(DP)を用いて効率的に解くことができます。基本的な考え方は以下の通りです。

• 配列全体の合計が奇数の場合、2つの等しい整数に分割することは不可能なので、即座に false を返します。
• 合計が偶数の場合、問題は「合計の半分の値を作れる部分集合が存在するか」という部分和問題に帰着できます。

アルゴリズムの手順

1. n := 配列のサイズとする
2. sum := 0 とし、すべての要素の合計を求める
3. sum が奇数なら false を返す
4. sum := sum / 2 とする
5. サイズ sum + 1 のブール型配列 dp を作成する
6. dp[0] := true と初期化する(何も選ばなければ和 0 は必ず作れる)
7. i を 0 から n − 1 まで繰り返す:
   • x := nums[i] とする
   • j を sum から x まで降順に繰り返し、dp[j] := dp[j] OR dp[j − x] と更新する
8. 最後に dp[sum] を返す

ここで重要なのは、内側のループを降順(j から x 方向)で回す点です。これにより、同じ要素を複数回使ってしまうことを防ぎ、各要素を高々1回しか使用しない0/1ナップサック型のDPとして正しく動作します。

C++での実装例

以下に実際の実装を示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool canPartition(vector<int>& nums) {
      int n = nums.size();
      int sum = 0;
      for(int i =0;i<n;i++)sum+=nums[i];
      if(sum&1)return false;
      sum/=2;
      vector <bool> dp(sum+1);
      dp[0] = true;
      for(int i =0;i<n;i++){
         int x = nums[i];
         for(int j =sum;j-x>=0;j--){
            dp[j]=dp[j] || dp[j-x];
         }
      }
      return dp[sum];
   }
};
main(){
   Solution ob;
   vector<int> v = {1,5,11,5};
   cout << ob.canPartition(v);
}

入力

[1,5,11,5]

出力

1

出力の 1 は true(分割可能)を意味します。

計算量について

• 時間計算量: O(n × sum/2)。要素数 n と目標の和に対してDPテーブルを更新するためです。
• 空間計算量: O(sum/2)。1次元のDP配列のみを使用するため、2次元テーブルを使う方法よりメモリ効率が良いのが特徴です。

まとめ

この問題は、配列の総和の半分を目標値とする部分和問題に変換することで、1次元DPによるシンプルな実装で解決できます。内側のループを降順に処理することが正しさのポイントとなるため、実装時には注意しましょう。