주어진 정수의 모든 고유한 분할(Partition)을 생성하는 C++ 프로그램

개요

이 글에서는 주어진 정수를 여러 개의 양의 정수 합으로 표현하는 모든 고유한 분할(unique partition)을 구하는 C++ 프로그램을 소개합니다. 예를 들어 4가 주어지면 4, 3+1, 2+2, 2+1+1, 1+1+1+1처럼 순서만 다른 중복 조합은 제외하고 각 분할의 합이 원래 수가 되는 모든 경우를 출력합니다.

알고리즘

핵심 아이디어는 첫 번째 분할을 '숫자 자기 자신'으로 초기화한 뒤, 규칙에 따라 다음 분할을 하나씩 생성하며 마지막 분할(모두 1로만 이루어진 경우)에 도달할 때까지 반복하는 것입니다.

시작
함수 displayAllUniqueParts(int m):
    1) 분할에서 마지막 요소의 인덱스 k를 0으로 설정
    2) 첫 번째 분할을 숫자 자기 자신으로 초기화: p[k] = m
    3) 현재 분할을 출력한 뒤 다음 분할을 생성하는 while 루프 작성.
       현재 분할이 모두 1로 이루어지면 루프 종료
    4) displayArray(p, k + 1)로 현재 분할 출력
    5) 다음 분할 생성:
    6) val = 0으로 초기화.
       p[]에서 가장 오른쪽에 있는 1이 아닌 값을 찾고,
       추가로 수용 가능한 값의 크기를 알 수 있도록 val 갱신.
       만약 k < 0이면 모든 값이 1이므로 더 이상 분할 없음 → 종료
       찾은 p[k]를 1 감소시키고 val 조정
    7) val이 p[k]보다 크면 내림차순 정렬 규칙이 깨짐.
       val을 p[k] 크기 이하의 여러 값으로 나누어 p[k] 뒤 위치에 복사.
       val을 다음 위치에 복사하고 위치 증가
끝

예제 코드

#include<iostream>
using namespace std;

void displayArray(int p[], int m) // 배열 출력 함수
{
    for (int i = 0; i < m; i++)
        cout << p[i] << " ";
    cout << endl;
}

void displayAllUniqueParts(int m)
{
    int p[m];      // 가변 길이 배열(VLA) 사용 — GCC 확장 기능
    int k = 0;
    p[k] = m;

    while (true)
    {
        displayArray(p, k + 1);   // 현재 분할 출력

        int val = 0;              // val 초기화
        while (k >= 0 && p[k] == 1)
        {
            val += p[k];          // val 갱신
            k--;
        }

        if (k < 0)
            return;               // 모든 분할 완료

        p[k]--;
        val++;

        while (val > p[k])        // val이 더 큰 경우
        {
            p[k + 1] = p[k];
            val = val - p[k];
            k++;
        }
        p[k + 1] = val;
        k++;
    }
}

int main()
{
    cout << "Display All Unique Partitions of 3\n";
    displayAllUniqueParts(3);

    cout << "\nDisplay All Unique Partitions of 4\n";
    displayAllUniqueParts(4);

    cout << "\nDisplay All Unique Partitions of 5\n";
    displayAllUniqueParts(5);

    return 0;
}

실행 결과

Display All Unique Partitions of 3
3
2 1
1 1 1

Display All Unique Partitions of 4
4
3 1
2 2
2 1 1
1 1 1 1

Display All Unique Partitions of 5
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1

참고 사항

위 코드의 int p[m]은 가변 길이 배열(VLA)로, 표준 C++이 아니라 GCC 등 일부 컴파일러에서 지원하는 확장 기능입니다. 표준을 준수하려면 vector<int>나 동적 할당(new int[m])을 사용하는 것이 좋습니다. 또한 이 알고리즘은 각 단계에서 이전 분할을 기반으로 다음 분할을 만들어 내므로, 전체 분할 개수인 분할수(p(n))에 비례하는 시간 복잡도를 가집니다.