C++ – 부호를 바꿔 합이 M으로 나누어떨어지는 N개 요소의 모든 조합 출력하기

이 문제에서는 N개의 요소로 이루어진 배열이 주어집니다. 각 요소 앞에 '+' 또는 '-' 부호를 붙여 만들 수 있는 모든 조합을 검토한 뒤, 그 합이 주어진 정수 M으로 나누어떨어지는 조합을 모두 찾아 출력하는 것이 목표입니다.

문제 예시

입력 : arr[] = {4, 7, 3}, M = 3
출력 :
- 4 + 7 - 3   (합 = 0)
- 4 + 7 + 3   (합 = 6)
+ 4 - 7 - 3   (합 = -6)
+ 4 - 7 + 3   (합 = 0)

위 예시에서 네 가지 부호 조합의 합은 각각 0, 6, -6, 0으로 모두 3으로 나누어떨어지므로 전부 출력됩니다.

이 문제를 효율적으로 해결하려면 멱집합(power set) 개념을 활용해야 합니다. 멱집합은 한 집합이 가질 수 있는 모든 부분집합의 집합을 의미하며, 이를 비트마스크 기법과 결합하면 각 요소에 붙일 부호의 2^N가지 조합을 체계적으로 생성할 수 있습니다. 각 조합마다 합을 계산한 후 M으로 나누어떨어지는 경우만 골라 부호와 함께 출력하면 됩니다.

알고리즘

1단계: 비트마스크(멱집합)를 이용해 '+'와 '-'의 모든 조합을 순회합니다.
2단계: 각 조합에 대해 요소들의 합을 계산합니다.
3단계: 합이 M으로 나누어떨어지면 해당 부호 조합을 출력합니다.

C++ 구현 예제

#include <iostream>
using namespace std;

void printDivisibleSum(int a[], int n, int m){
    // 2^n가지 부호 조합을 비트마스크로 순회
    for (int i = 0; i < (1 << n); i++) {
        int sum = 0;
        int num = 1 << (n - 1);
        for (int j = 0; j < n; j++) {
            if (i & num)
                sum += a[j];      // 비트가 1이면 '+'
            else
                sum += (-1 * a[j]); // 비트가 0이면 '-'
            num = num >> 1;
        }
        // 합이 M으로 나누어떨어지면 조합 출력
        if (sum % m == 0) {
            num = 1 << (n - 1);
            for (int j = 0; j < n; j++) {
                if ((i & num))
                    cout << "+ " << a[j] << " ";
                else
                    cout << "- " << a[j] << " ";
                num = num >> 1;
            }
            cout << endl;
        }
    }
}

int main(){
    int arr[] = {4, 7, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 3;
    cout << "M으로 나누어떨어지는 합의 조합 :\n";
    printDivisibleSum(arr, n, m);
    return 0;
}

실행 결과

- 4 + 7 - 3
- 4 + 7 + 3
+ 4 - 7 - 3
+ 4 - 7 + 3

시간 복잡도

가능한 부호 조합은 총 2^N가지이며, 각 조합마다 합을 계산하고 출력하는 데 O(N)의 시간이 소요되므로 전체 시간 복잡도는 O(2^N × N)입니다. 따라서 이 방법은 N이 작은 경우에 적합하며, N이 커질수록 조합의 수가 지수적으로 증가한다는 점을 유의해야 합니다.