C++를 이용해 주어진 숫자 목록에서 만들 수 있는 모든 가능한 조합을 생성하는 프로그램을 소개합니다. 이 프로그램은 재귀 호출을 활용하여 길이가 1인 조합부터 원소 개수(n)와 같은 길이의 조합까지 차례대로 출력합니다.
동작 원리 (알고리즘)
조합 생성의 핵심은 각 원소에 대해 ‘포함한다 / 포함하지 않는다’라는 두 가지 선택을 반복적으로 적용하는 것입니다. 이 과정을 재귀 함수로 구현하면 다음과 같습니다.
시작
원소의 개수와 각 원소를 입력받는다.
함수 Combi(char a[], int reqLen, int s, int currLen, bool check[], int l):
① 만약 currLen > reqLen이면 → 반환한다.
② 그렇지 않고 currLen == reqLen이면 → 새로 생성된 조합을 출력한다.
③ 만약 s == l이면 → 더 이상 남은 원소가 없으므로 반환한다.
④ 각 인덱스마다 두 가지 선택지가 있다.
- 해당 원소를 ‘true’(포함)로 표시하고, currLen과 s를 증가시킨 채 Combi()를 재귀 호출한다.
- 해당 원소를 ‘false’(제외)로 표시하고, s만 증가시킨 채 Combi()를 재귀 호출한다.
끝
예제 코드
#include<iostream>
using namespace std;
// 주어진 배열 집합의 가능한 모든 조합을 출력하는 함수
void Combi(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;
// 현재 원소를 포함(true)하는 경우: 'currLen'과 's'를 증가시켜 재귀 호출
Combi(a, reqLen, s + 1, currLen + 1, check, l);
check[s] = false;
// 현재 원소를 제외(false)하는 경우: 's'만 증가시켜 재귀 호출
Combi(a, reqLen, s + 1, currLen, check, l);
}
int main() {
int i, n;
cout<<"배열의 원소 개수를 입력하세요: ";
cin>>n;
char a[n];
bool check[n];
cout<<"\n";
for(i = 0; i < n; i++) {
cout<<i+1<<"번째 원소 입력: ";
cin>>a[i];
check[i] = false;
}
for(i = 1; i <= n; i++) {
cout<<"\n길이 "<<i<<"인 모든 가능한 조합:\n";
Combi(a, i, 0, 0, check, n);
}
return 0;
}
실행 결과
배열의 원소 개수를 입력하세요: 4 1번째 원소 입력: 4 2번째 원소 입력: 3 3번째 원소 입력: 2 4번째 원소 입력: 1 길이 1인 모든 가능한 조합: 4 3 2 1 길이 2인 모든 가능한 조합: 4 3 4 2 4 1 3 2 3 1 2 1 길이 3인 모든 가능한 조합: 4 3 2 4 3 1 4 2 1 3 2 1 길이 4인 모든 가능한 조합: 4 3 2 1
코드 핵심 정리
Combi() 함수는 세 가지 매개변수를 중심으로 동작합니다.
- s: 현재 검토 중인 배열의 인덱스
- currLen: 지금까지 선택된 원소의 개수
- reqLen: 만들고자 하는 조합의 목표 길이
배열 check[]는 각 원소의 포함 여부를 저장하며, currLen이 reqLen에 도달하는 순간 true로 표시된 원소들만 출력해 하나의 조합을 완성합니다. 이처럼 포함/제외 분기를 재귀적으로 반복하는 방식 덕분에 중복 없이 모든 조합을 빠짐없이 생성할 수 있습니다. 참고로 원본 코드에서는 원소 개수를 입력받기 전에 check 배열이 선언되어 있었지만, 위 예제에서는 n을 먼저 입력받은 후 배열을 선언하도록 수정하여 안전하게 동작하도록 정리했습니다.