C++で解くパーティション問題：配列を合計が等しい2つの部分集合に分割できるか判定する方法

パーティション問題とは

パーティション問題とは、与えられた配列を、それぞれの要素の合計が完全に一致する2つの部分集合に分割できるかどうかを判定する問題です。この問題は「部分和問題（Subset Sum Problem）」の変形であり、部分和問題はさらに「ナップサック問題」の変形にあたります。ここではC++を使ってこの問題を解き、条件が満たされるかどうかに応じて結果を出力するプログラムを作成します。

入力例

arr[] = {6, 4, 8, 12, 15}

出力例

Is impossible to divide into two subsets of equal sum

この入力例では、配列の合計が 6+4+8+12+15 = 45 となり奇数であるため、2つの等しい部分集合への分割は不可能です。

解法アプローチ1：再帰による解法

まず、配列内の全要素の合計を求めます。合計が奇数の場合、2つの等しい部分集合には分割できません。合計が偶数の場合は、「合計の半分（sum/2）」となる部分集合が存在するかを調べます。各要素を順番に検討し、次の2つの選択肢のいずれかを選びます。

• 現在の要素を部分集合に含め、残りの要素で目標の合計に到達できるか試す。
• 現在の要素を部分集合から除外し、残りの要素に対して同じ処理を繰り返す。

現在の要素を含める場合・除外する場合のどちらかで部分集合が見つかれば true を返し、どちらでも見つからなければ false を返します。再帰は、要素がなくなったとき、または合計が負になったときに終了します。合計がちょうど0になった場合は、目的の部分集合が見つかったことを意味する true を返します。

実装例

#include <bits/stdc++.h>
using namespace std;
bool isSubsetSum(int arr[], int n, int sum) {
    if (sum == 0)
        return true;
    if (n == 0 && sum != 0)
        return false;
    if (arr[n - 1] > sum)
        return isSubsetSum(arr, n - 1, sum);
    return isSubsetSum(arr, n - 1, sum) ||
        isSubsetSum(arr, n - 1, sum - arr[n - 1]);
}
bool findPartiion(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
    if (sum % 2 != 0)
        return false;
    return isSubsetSum(arr, n, sum / 2);
}
int main() {
    int arr[] = {
        6,
        4,
        8,
        12,
        15
    };
    int n = sizeof(arr) / sizeof(arr[0]);
    if (findPartiion(arr, n) == true)
        cout << "Is possible to divide into two subsets " "of equal sum";
    else
        cout << "Is impossible to divide into two subsets" " of equal sum";
    return 0;
}

出力

Is impossible to divide into two subsets of equal sum

解法アプローチ2：動的計画法（DP）による解法

要素の合計がそれほど大きくない場合は、動的計画法を用いることで効率的に解けます。「その合計値を、これまで処理した要素だけで作れるかどうか」を記録するDP表を作成し、ボトムアップ方式で順に埋めていくことで解を構築できます。理論上はサイズ (sum/2 + 1) × (n + 1) の2次元配列を使用しますが、実装の工夫により1次元配列だけでも十分であり、メモリ使用量を削減できます。

実装例

#include <bits/stdc++.h>
using namespace std;
bool findPartiion(int arr[], int n) {
    int sum = 0;
    int i, j;
    for (i = 0; i < n; i++)
        sum += arr[i];
    if (sum % 2 != 0)
        return false;
    bool part[sum / 2 + 1];
    for (i = 0; i <= sum / 2; i++) {
        part[i] = 0;
    }
    for (i = 0; i < n; i++) {
        for (j = sum / 2; j >= arr[i]; j--) {
            if (part[j - arr[i]] == 1 || j == arr[i])
                part[j] = 1;
        }
    }
    return part[sum / 2];
}
int main() {
    int arr[] = {
        6,
        4,
        8,
        12,
        15
    };
    int n = sizeof(arr) / sizeof(arr[0]);
    if (findPartiion(arr, n) == true)
        cout << "Is possible to divide into two subsets of equal " "sum";
    else
        cout << "Is impossible to divide into two subsets" " of equal sum";
    return 0;
}

出力

Is impossible to divide into two subsets of equal sum

まとめ

この記事では、パーティション問題の考え方と、C++による2つの実装方法（再帰・動的計画法）を学びました。同じロジックはJavaやPythonなど他の言語でも同様に実装できます。再帰によるアプローチは直感的で理解しやすい基本的な手法ですが、動的計画法を組み合わせることで計算量を大幅に削減できます。パーティション問題は、タスクの均等割り当てやリソース配分など、実際の開発現場でも応用される重要なアルゴリズムの基礎です。