C++ 재귀로 합이 n이 되는 모든 양의 정수 조합 찾기

양의 정수 n이 주어졌을 때, 각 요소의 합이 정확히 n이 되는 모든 양의 정수 조합을 찾아야 합니다. 이때 순서만 다른 경우는 같은 조합으로 간주하므로, 순열(permutation)이 아닌 조합(combination)만을 대상으로 합니다.

예를 들어 n = 4라면 가능한 조합은 [1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]의 다섯 가지입니다.

접근 방법

이 문제는 재귀(recursion)를 이용해 효율적으로 해결할 수 있습니다. 조합을 저장할 배열을 하나 준비한 뒤, 재귀 호출을 통해 배열을 차례대로 채워 나갑니다. 각 조합은 요소가 오름차순으로 저장되도록 구성하며, 이렇게 하면 동일한 조합이 중복해서 생성되는 것을 자연스럽게 방지할 수 있습니다.

동작 원리

핵심 함수인 getCombination은 아래와 같은 규칙으로 동작합니다.

- 남은 합(decrement)이 음수가 되면 해당 경로는 유효하지 않으므로 즉시 종료합니다.
- 남은 합이 정확히 0이면 목표값 n에 도달한 것이므로, 배열에 저장된 조합을 출력합니다.
- 새로 추가할 값 k는 첫 번째 위치에서는 1부터, 그 이후에는 직전 요소 값부터 n까지의 범위에서 선택합니다. 이전 요소보다 작은 값을 허용하지 않기 때문에 모든 조합이 오름차순을 유지하게 됩니다.

예제 코드

#include<iostream>
using namespace std;

void getCombination(int arr[], int index, int num, int decrement) {
    if (decrement < 0)
        return;
    if (decrement == 0) {
        for (int i = 0; i < index; i++)
            cout << arr[i] << " ";
        cout << endl;
        return;
    }
    int prev;
    if (index == 0)
        prev = 1;
    else
        prev = arr[index - 1];
    for (int k = prev; k <= num; k++) {
        arr[index] = k;
        getCombination(arr, index + 1, num, decrement - k);
    }
}

void findCombinations(int n) {
    int arr[n];
    getCombination(arr, 0, n, n);
}

int main() {
    int n = 4;
    findCombinations(n);
}

실행 결과

1 1 1 1
1 1 2
1 3
2 2
4

출력 결과에서 볼 수 있듯이, 각 조합은 오름차순으로 정렬되어 있으며 순서만 다른 중복 조합은 포함되지 않습니다. 이 알고리즘은 n이 커질수록 조합의 개수가 빠르게 증가하는 분할 문제(partition problem)의 성격을 가지므로, 지수적으로 늘어나는 탐색 공간을 재귀로 처리한다는 점을 기억하면 좋습니다.