C++で-1と+1の配列に合計が0のサイズKのサブセットがあるかどうかを調べます

この問題では、1と-1のみで構成される配列arr[]と整数値kが与えられます。私たちのタスクは、-1と+1の配列に合計が0のサイズKのサブセットがあるかどうかを見つけることです。

問題を理解するために例を見てみましょう

入力： arr [] ={-1、1、-1、-1、1、1、-1}、k =4

出力： はい

説明：

サイズ4のサブセット{-1、1、-1、1}。合計=-1+ 1-1 + 1 =0

ソリューションアプローチ：

合計が0に等しいサイズkのサブセットが存在するかどうかを確認する必要があります。サブセットとして、配列の任意の要素を考慮することができます。1と-1の数が等しい場合、合計は0になります。サブセット。これは、サブセットのサイズが偶数の場合にのみ可能です。

簡単に、

kが偶数の場合、trueを返します。
kが奇数の場合、falseを返します。

ソリューションの動作を説明するプログラム

例

#include <iostream>
using namespace std;

int countOne(int a[], int n) {
   
   int i, count = 0;
   for (i = 0; i < n; i++)
      if (a[i] == 1)
         count++;
   return count;
}

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.