ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ซึ่งประกอบด้วย 1 และ -1 และค่าจำนวนเต็ม k เท่านั้น งานของเราคือ ค้นหาว่ามีส่วนย่อยของขนาด K ที่มีผลรวม 0 ในอาร์เรย์ -1 และ +1 หรือไม่
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล: 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.
