इस समस्या में, हमें एक सरणी arr[] दी गई है जिसमें केवल 1 और -1 हैं और एक पूर्णांक मान k। हमारा कार्य जांचना है कि क्या -1 और +1 की सरणी में आकार 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 के बराबर है। चूंकि उपसमुच्चय के रूप में हम सरणी से किसी भी तत्व पर विचार कर सकते हैं, योग 0 होगा यदि उपसमुच्चय में 1 और -1 की समान संख्या हो। यह केवल तभी संभव है जब उपसमुच्चय का आकार सम हो।
सरलता से,
यदि 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.
