数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 C++ 中查找数组中是否存在大小为 K 且和为 0 的子集（数组中只有 -1 和 +1）
在这个问题中，我们给定一个仅包含 1 和 -1 的数组 arr[] 和一个整数 k。我们的任务是 *查找数组中是否存在大小为 K 且和为 0 的子集*。
让我们举个例子来理解这个问题：
输入：arr[] = {-1, 1, -1, -1, 1 , 1, -1}, k = 4
输出：YES
解释
大小为 4 的子集，{-1, 1, -1, 1}。和 = -1 + 1 - 1 + 1 = 0
解决方案：
我们需要检查是否存在任何大小为 k 且和等于 0 的子集。作为一个子集，我们可以考虑数组中的任何元素，如果子集中 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.
更新于： 2021年1月22日
120 次查看
广告