在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.