【C++】-1と+1からなる配列に、合計が0となるサイズKの部分集合が存在するか判定する方法

この問題では、1と-1のみから構成される配列 arr[] と整数値 k が与えられます。私たちのタスクは、-1と+1からなる配列の中に、合計が0となるサイズKの部分集合が存在するかどうかを判定することです。

問題例で理解しよう

入力: arr[] = {-1, 1, -1, -1, 1, 1, -1}, k = 4

出力: YES

説明:

サイズ4の部分集合 {-1, 1, -1, 1} を選ぶと、合計 = -1 + 1 - 1 + 1 = 0 となります。

解法の考え方

まず、合計が0になるサイズKの部分集合が存在するかどうかを確認する必要があります。部分集合には配列の任意の要素を選べるため、部分集合内に「1」と「-1」が同数含まれていれば、その合計は必ず0になります。

ここで重要なのは、1と-1を同数ずつ含むためには、部分集合のサイズKが偶数でなければならないという点です。さらに、実際に部分集合を組み立てられるかどうかは、配列全体に含まれる1の個数と-1の個数が、それぞれK/2個以上あるかどうかで決まります。

まとめると、以下の条件をすべて満たす場合に「YES」を返せます。
・Kが偶数である
・配列中の1の個数が K/2 以上である
・配列中の-1の個数が K/2 以上である

いずれかの条件でも満たさない場合は、条件を満たす部分集合は存在しません。

解法の実装プログラム

C++コード例

#include <iostream>
using namespace std;

// 配列内の1の個数を数える関数
int countOne(int a[], int n) {
   int i, count = 0;
   for (i = 0; i < n; i++)
      if (a[i] == 1)
         count++;
   return count;
}

// 合計が0となるサイズKの部分集合が存在するか判定する関数
bool isSubSetSumZeroFound(int arr[], int n, int K) {
   int totalOne = countOne(arr, n);
   int totalNegOne = n - totalOne;
   return (K % 2 == 0 && totalOne >= K / 2 && totalNegOne >= K / 2);
}

int main() {
   int arr[] = { 1, 1, -1, -1, 1, -1, 1, 1, -1 };
   int size = sizeof(arr) / sizeof(arr[0]);
   int K = 4;
   if (isSubSetSumZeroFound(arr, size, K))
      cout<<"Subset of size "<<K<<" with sum of all elements 0 exists.";
   else
      cout<<"No subset found";
   return 0;
}

実行結果

Subset of size 4 with sum of all elements 0 exists.

この出力は、「全要素の合計が0となるサイズ4の部分集合が存在する」ことを意味しています。

まとめ

本解法のポイントは、部分集合の合計が0になるためには1と-1が同数必要であることに着目し、Kの偶奇と各値の出現回数だけで判定できる点です。配列を一度走査するだけなので、時間計算量はO(n)、空間計算量はO(1)と非常に効率的です。