Kiểm tra tập con kích thước K tổng bằng 0 trong mảng -1 và +1 C++

Cho mảng chỉ chứa 1 và -1, và số k. Nhiệm vụ: kiểm tra có tập con kích thước k tổng bằng 0 không.

Ví dụ:

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

Đầu ra: YES

Giải thích: Tập con {-1, 1, -1, 1} tổng = 0.

Phương pháp giải

Tổng bằng 0 <=> số lượng 1 và -1 trong tập con bằng nhau => k phải chẵn. Ngoài ra mảng phải đủ cả 1 và -1.

Điều kiện: k chẵn VÀ số lượng 1 >= k/2 VÀ số lượng -1 >= k/2.

Chương trình minh họa

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

Kết quả

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