Tìm xem có bất kỳ tập con nào có kích thước K với tổng bằng 0 trong mảng -1 và +1 trong C ++ hay không

Trong bài toán này, chúng ta được cung cấp một mảng arr [] chỉ gồm 1 và -1 và một giá trị nguyên k. Nhiệm vụ của chúng ta là tìm xem có bất kỳ tập con nào có kích thước K với tổng bằng 0 trong mảng -1 và +1 hay không.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào: arr [] ={-1, 1, -1, -1, 1, 1, -1}, k =4

Đầu ra: CÓ

Giải thích:

Tập hợp con có kích thước 4, {-1, 1, -1, 1}. Tổng =-1 + 1 - 1 + 1 =0

Phương pháp tiếp cận giải pháp:

Chúng ta cần kiểm tra xem có tồn tại bất kỳ tập con nào có kích thước k có tổng bằng 0. Là một tập con, chúng ta có thể xem xét bất kỳ phần tử nào từ mảng, tổng sẽ bằng 0, nếu có một số bằng 1 và -1 trong tập hợp con. Điều này chỉ có thể thực hiện được nếu kích thước của tập hợp con là chẵn.

Đơn giản,

Nếu k là chẵn, trả về true.
Nếu k là số lẻ, trả về false.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

Subset of size 4 with sum of all elements 0 exists.