ตรวจสอบว่ามีซับเซ็ตขนาด K ผลรวมเป็น 0 ในอาร์เรย์ -1 และ +1 ใน C++

โจทย์

ได้รับอาร์เรย์ที่มีแค่ -1 และ +1 และจำนวน k ทางเราต้อง ตรวจสอบว่ามีซับเซ็ตขนาด k ที่ผลรวมเป็น 0 หรือไม่

ตัวอย่าง

Input: arr[] = {-1, 1, -1, -1, 1, 1, -1}, k = 4

Output: YES

อธิบาย: ซับเซ็ต {-1, 1, -1, 1} ผลรวม = 0

แนวทางแก้ปัญหา

ผลรวมเป็น 0 ได้ก็ต่อเมื่อมี -1 และ +1 เท่ากัน -> k ต้องเป็นเลขคู่

นอกจากนี้ ต้องมี -1 และ +1 เพียงพอในอาร์เรย์ (แต่ละอย่าง ≥ k/2)

โปรแกรมตัวอย่าง

#include <iostream>
using namespace std;

int countOne(int a[], int n) {
    int count = 0;
    for (int 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.