在C ++中的-1和+1数组中查找是否有大小为K的子集且总和为0

在这个问题中，我们得到了一个仅由1和-1以及整数k组成的数组arr []。我们的任务是查找在-1和+1数组中是否存在大小为K的子集且总和为0。 

让我们举个例子来了解这个问题，

输入：  arr [] = {-1，1，-1，-1，1，1，-1}，k = 4

输出： 是

解释：

大小为4的子集，{-1，1，-1，1}。总和= -1 + 1-1 + 1 = 0

解决方法： 

我们需要检查是否存在任何大小为k的子集，其总和等于0。作为子集，我们可以考虑数组中的任何元素，如果in中有相等的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<<"大小子集 "<<K<<" with sum of all elements 0 exists.";
   else
      cout<<"No subset found";
   return 0;
}

大小子集 4 with sum of all elements 0 exists.