এই সমস্যায়, আমাদেরকে একটি অ্যারে দেওয়া হয়েছে যা শুধুমাত্র 1 এবং -1 এবং একটি পূর্ণসংখ্যার মান k নিয়ে গঠিত। আমাদের কাজ হল -1 এবং +1 এর অ্যারেতে 0 যোগ সহ K আকারের কোনো উপসেট আছে কিনা তা খুঁজে বের করা।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট: arr[] ={-1, 1, -1, -1, 1, 1, -1}, k =4
আউটপুট: হ্যাঁ
ব্যাখ্যা:
সাইজ 4, {-1, 1, -1, 1} এর উপসেট। যোগফল =-1 + 1 - 1 + 1 =0
সমাধান পদ্ধতি:
আমাদের চেক করতে হবে যে আকারের k আকারের কোনো উপসেট আছে কিনা যার যোগফল 0 এর সমান। একটি উপসেট হিসাবে আমরা অ্যারের যেকোনো উপাদান বিবেচনা করতে পারি, যোগফল হবে 0, যদি 1 এবং -1 এর সমান সংখ্যা থাকে উপসেট উপসেটের আকার সমান হলেই এটি সম্ভব।
সহজভাবে,
k জোড় হলে, সত্য ফেরত দিন।
k বিজোড় হলে মিথ্যা ফেরত দিন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#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.
