資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告