이 글에서는 C++를 사용하여 주어진 집합에서 정확히 k개의 요소를 포함하는 모든 가능한 부분 집합(조합)을 생성하는 방법을 알아봅니다. 재귀 호출과 백트래킹(backtracking) 기법을 활용해 각 요소를 부분 집합에 포함할지 여부를 결정함으로써 문제를 해결합니다.
알고리즘
시작
함수 PossibleSubSet(char a[], int reqLen, int s, int currLen, bool check[], int l)
만약 currLen > reqLen 이면
반환
아니면 currLen == reqLen 이면
새로 생성된 수열을 출력
만약 s == l 이면
더 이상 남은 요소가 없으므로 반환
각 인덱스마다 두 가지 선택지가 존재:
1) 해당 위치를 'true'로 표시하고, 'currLen'과 's'를 증가시킨 채 PossibleSubSet()을 재귀 호출
2) 해당 위치를 'false'로 표시하고, 's'만 증가시킨 채 PossibleSubSet()을 재귀 호출
끝
동작 원리
핵심 아이디어는 백트래킹입니다. 배열의 각 인덱스에 대해 항상 두 가지 경우를 모두 탐색합니다.
- 포함하는 경우: 현재 요소를 부분 집합에 넣고(currLen + 1), 다음 인덱스로 진행합니다.
- 포함하지 않는 경우: 현재 요소를 건너뛰고(currLen 유지), 다음 인덱스로만 진행합니다.
선택된 요소의 개수(currLen)가 요구되는 길이(reqLen)에 도달하면, check 배열을 참조하여 실제로 선택된 요소들을 출력합니다. 이 과정을 통해 중복 없이 모든 조합을 빠짐없이 탐색할 수 있습니다.
예제 코드
#include<iostream>
using namespace std;
// 주어진 배열 집합의 모든 가능한 조합을 출력하는 함수
void PossibleSubSet(char a[], int reqLen, int s, int currLen, bool check[], int l) {
if (currLen > reqLen)
return;
else if (currLen == reqLen) {
cout << "\t";
for (int i = 0; i < l; i++) {
if (check[i] == true) {
cout << a[i] << " ";
}
}
cout << "\n";
return;
}
if (s == l) {
return;
}
check[s] = true;
// 'currLen'과 's'를 증가시켜 PossibleSubSet()을 재귀 호출
PossibleSubSet(a, reqLen, s + 1, currLen + 1, check, l);
check[s] = false;
// 's'만 증가시켜 PossibleSubSet()을 재귀 호출
PossibleSubSet(a, reqLen, s + 1, currLen, check, l);
}
int main() {
int i, n, m;
cout << "Enter the number of elements: ";
cin >> n;
bool *check = new bool[n];
char *a = new char[n];
cout << "\n";
for (i = 0; i < n; i++) {
cout << "Enter " << i + 1 << " element: ";
cin >> a[i];
check[i] = false;
}
cout << "\nEnter the length of the subsets required: ";
cin >> m;
cout << "\nThe possible combination of length " << m << " for the given array set:\n";
PossibleSubSet(a, m, 0, 0, check, n);
delete[] check;
delete[] a;
return 0;
}
참고: 원본 코드에서는 배열 크기 n이 입력되기 전에 배열이 선언되어 있었지만, 올바른 동작을 위해 사용자 입력을 받은 후 동적 할당으로 수정했습니다.
실행 결과
Enter the number of elements: 7 Enter 1 element: 7 Enter 2 element: 6 Enter 3 element: 5 Enter 4 element: 4 Enter 5 element: 3 Enter 6 element: 2 Enter 7 element: 1 Enter the length of the subsets required: 6 The possible combination of length 6 for the given array set: 7 6 5 4 3 2 7 6 5 4 3 1 7 6 5 4 2 1 7 6 5 3 2 1 7 6 4 3 2 1 7 5 4 3 2 1 6 5 4 3 2 1
복잡도 분석
n개의 요소 중 k개를 선택하는 조합의 총 개수는 이항 계수 C(n, k)이므로, 시간 복잡도는 대략 O(C(n, k) × k)입니다. 공간 복잡도는 재귀 호출 스택과 check 배열에 의해 O(n)입니다. 따라서 n이 커질수록 조합의 수가 급격히 늘어나므로, 입력 크기를 적절히 제한하는 것이 좋습니다.