이 문제에서는 1과 -1과 정수 값 k로 구성된 배열 arr[]이 제공됩니다. 우리의 임무는 -1과 +1의 배열에서 합이 0인 크기 K의 하위 집합이 있는지 찾는 것입니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
입력: arr[] ={-1, 1, -1, -1, 1, 1, -1}, k =4
출력: 예
설명:
크기 4, {-1, 1, -1, 1}의 하위 집합입니다. 합계 =-1 + 1 - 1 + 1 =0
해결 방법:
합이 0인 크기 k의 부분 집합이 있는지 확인해야 합니다. 부분 집합으로 배열의 모든 요소를 고려할 수 있으므로 1과 -1의 수가 같으면 합은 0이 됩니다. 하위 집합입니다. 이것은 부분집합의 크기가 짝수인 경우에만 가능합니다.
간단히
k가 짝수이면 true를 반환합니다.
k가 홀수이면 false를 반환합니다.
우리 솔루션의 작동을 설명하는 프로그램,
예
#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.