C++로 배열의 주어진 크기에 해당하는 모든 부분집합 출력하기

이 문제에서는 하나의 배열이 주어지며, 배열의 원소들을 사용해 만들 수 있는 크기 r의 모든 부분집합(subset)을 출력해야 합니다.

문제 이해하기

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

입력:
array = {3, 5, 6}
r = 2

출력:
3 5
3 6
5 6

즉, 배열에 있는 숫자들로 만들 수 있는 모든 조합을 찾되, 그중에서 정확히 r개의 원소를 가진 조합만 골라내는 것입니다. 같은 조합이 중복해서 출력되지 않도록 주의해야 합니다.

접근 방법

가장 일반적인 해결 방법은 재귀(recursion)를 활용하는 것입니다. 각 원소에 대해 두 가지 선택지를 고려합니다.

• 현재 원소를 부분집합에 포함시키는 경우
• 현재 원소를 부분집합에 포함시키지 않는 경우

이렇게 분기를 나누어 탐색하다가, 임시 배열(data)에 저장된 원소의 개수가 r에 도달하면 해당 부분집합을 출력합니다. 이 방식은 자연스럽게 중복 조합을 제거하면서 모든 경우의 수를 탐색할 수 있습니다.

C++ 구현 코드

#include <iostream>
using namespace std;

void printSubset(int arr[], int n, int r, int index, int data[], int i);

int main(){
    int arr[] = {3, 5, 6};
    int r = 2;
    cout<<"The sets are : ";
    int n = sizeof(arr) / sizeof(arr[0]);
    int data[r];
    printSubset(arr, n, r, 0, data, 0);
    return 0;
}

void printSubset(int arr[], int n, int r, int index, int data[], int i){
    // r개의 원소를 모두 선택했으면 출력
    if (index == r) {
        for (int j = 0; j < r; j++)
            cout<<data[j]<<" ";
        cout<<endl;
        return;
    }
    // 더 이상 선택할 원소가 없으면 종료
    if (i >= n)
        return;
    // 현재 원소를 포함하는 경우
    data[index] = arr[i];
    printSubset(arr, n, r, index + 1, data, i + 1);
    // 현재 원소를 포함하지 않는 경우
    printSubset(arr, n, r, index, data, i + 1);
}

실행 결과

The sets are :
3 5
3 6
5 6

코드 설명

printSubset 함수는 다음과 같은 매개변수를 받습니다.

• arr[]: 입력 배열
• n: 배열의 크기
• r: 만들고자 하는 부분집합의 크기
• index: 현재까지 data 배열에 채워진 원소의 개수
• data[]: 현재 진행 중인 부분집합을 저장하는 임시 배열
• i: 현재 검토 중인 배열 원소의 인덱스

재귀 호출을 통해 각 원소를 포함하는 경우와 포함하지 않는 경우를 모두 탐색하므로, 시간 복잡도는 O(2ⁿ)입니다. n이 커질수록 연산량이 급격히 늘어나므로, 입력 크기가 작은 경우에 적합한 방법입니다.