C++로 크기 n인 배열에서 r개 원소의 모든 조합 출력하기

이 문제에서는 크기가 n인 배열과 양의 정수 r이 주어지며, 배열 원소 중에서 r개를 선택하는 가능한 모든 조합을 출력하는 것이 목표입니다.

예시를 통해 문제를 이해해 보겠습니다.

입력: {5, 6, 7, 8}, r = 3
출력: {5, 6, 7}, {5, 6, 8}, {5, 7, 8}, {6, 7, 8}

접근 방법 1: 원소를 고정한 뒤 재귀 호출

이 문제를 해결하는 한 가지 방법은 특정 원소를 고정하고, 나머지 원소들을 순회하거나 재귀적으로 탐색하여 모든 조합을 찾는 것입니다. 이때 첫 번째 원소부터 n-r+1번째 원소까지만 고정하면 되며, 그 이후의 원소들은 나머지 조합을 만드는 과정에서 자연스럽게 처리됩니다.

아래는 이 방식을 구현한 C++ 코드입니다.

#include <iostream>
using namespace std;

void printRElementCombination(int arr[], int combination[], int start,
    int end, int index, int r) {
    if (index == r) {
        cout << "{ ";
        for (int j = 0; j < r; j++)
            cout << combination[j] << " ";
        cout << "}\t";
        return;
    }
    for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
        combination[index] = arr[i];
        printRElementCombination(arr, combination, i + 1, end, index + 1, r);
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int r = 3;
    int n = 5;
    int combination[r];
    cout << "조합 결과 : \n";
    printRElementCombination(arr, combination, 0, n - 1, 0, r);
}

출력

{ 1 2 3 } { 1 2 4 } { 1 2 5 } { 1 3 4 } { 1 3 5 } { 1 4 5 }
{ 2 3 4 } { 2 3 5 } { 2 4 5 } { 3 4 5 }

접근 방법 2: 현재 원소의 포함 여부를 확인

같은 문제를 해결하는 또 다른 방법은 현재 원소가 조합에 포함되는지 여부를 검사하면서, 필요한 크기의 모든 조합을 출력하는 것입니다. 기본 아이디어는 동일하게 각 원소를 재귀적으로 탐색하고 조합을 combo 배열에 저장하는 것이지만, 특정 원소를 미리 고정하지 않는다는 점이 다릅니다.

각 원소에 대해 두 가지 경우를 모두 시도합니다. 해당 원소를 조합에 포함하는 경우와 포함하지 않고 다음 원소로 넘어가는 경우입니다. 이렇게 하면 모든 조합을 빠짐없이 생성할 수 있습니다.

아래 프로그램을 통해 더 쉽게 이해할 수 있습니다.

#include <iostream>
using namespace std;

void combinationUtil(int arr[], int n, int r, int index, int combo[], int i) {
    if (index == r) {
        cout << "{";
        for (int j = 0; j < r; j++)
            cout << combo[j] << " ";
        cout << "}\t";
        return;
    }
    if (i >= n)
        return;
    // 현재 원소 arr[i]를 조합에 포함하는 경우
    combo[index] = arr[i];
    combinationUtil(arr, n, r, index + 1, combo, i + 1);
    // 현재 원소 arr[i]를 조합에 포함하지 않는 경우
    combinationUtil(arr, n, r, index, combo, i + 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int r = 3;
    int n = 5;
    int combo[r];
    cout << "조합 결과 : \n";
    combinationUtil(arr, n, r, 0, combo, 0);
    return 0;
}

출력

{1 2 3 }    {1 2 4 }    {1 2 5 }    {1 3 4 }    {1 3 5 }    {1 4 5 }
{2 3 4 }    {2 3 5 }    {2 4 5 }    {3 4 5 }

정리

두 방법 모두 재귀를 기반으로 하며, 시간 복잡도는 조합의 개수에 비례하여 O(nCr × r)입니다. 첫 번째 방법은 반복문과 재귀를 결합해 원소를 고정하는 방식이고, 두 번째 방법은 각 원소의 포함 여부를 분기 처리하는 순수한 부분집합 탐색 방식입니다. 상황에 따라 코드 가독성과 구현 편의성을 고려해 적절한 방법을 선택하면 됩니다.