C++로 -1과 +1 배열에서 합이 0이 되는 크기 K의 부분 집합 찾기

이 문제에서는 1과 -1로만 구성된 배열 arr[]와 정수 값 k가 주어집니다. 우리의 목표는 -1과 +1로 이루어진 배열에서 모든 원소의 합이 0이 되는 크기 K의 부분 집합(subset)이 존재하는지 판별하는 것입니다.

예제를 통한 문제 이해

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

출력: YES

설명:

크기가 4인 부분 집합 {-1, 1, -1, 1}을 살펴보면, 합계는 -1 + 1 - 1 + 1 = 0이 됩니다. 따라서 조건을 만족하는 부분 집합이 존재하므로 YES를 출력합니다.

해결 접근 방식

핵심 아이디어는 간단합니다. 부분 집합에는 배열의 어떤 원소든 포함될 수 있으며, 부분 집합의 합이 0이 되려면 1과 -1의 개수가 정확히 같아야 합니다. 그런데 두 수의 개수가 같으려면 전체 개수가 반드시 짝수여야 하므로, 크기가 홀수인 부분 집합은 절대 조건을 만족할 수 없습니다.

또한 배열에 실제로 1과 -1이 충분히 존재하는지도 확인해야 합니다. 즉, 배열 내 1의 개수와 -1의 개수가 각각 최소 K/2개 이상이어야 합니다.

이를 정리하면 다음과 같습니다.

• K가 홀수라면 → 합이 0인 부분 집합이 존재할 수 없으므로 false를 반환합니다.
• K가 짝수이면서, 배열에 1과 -1이 각각 K/2개 이상 있다면 → true를 반환합니다.
• 그 외의 경우 → false를 반환합니다.

이 알고리즘은 배열을 한 번만 순회하면 되므로 시간 복잡도는 O(n), 추가 공간 복잡도는 O(1)로 매우 효율적입니다.

솔루션 동작 예시 코드

C++ 구현 예제

#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.

위 코드에서 countOne 함수는 배열 내 1의 개수를 세고, isSubSetSumZeroFound 함수는 K의 짝수 여부와 함께 1 및 -1이 각각 K/2개 이상 존재하는지 검사하여 결과를 반환합니다. 이처럼 단순한 수학적 성질을 활용하면 별도의 탐색 없이도 문제를 상수 시간 논리 연산으로 해결할 수 있습니다.