C++로 a, b, c, d, e의 모든 조합 생성하기

이 프로그램은 a, b, c, d, e 다섯 개의 문자로부터 만들 수 있는 모든 조합을 생성하는 C++ 코드입니다. 재귀 호출과 백트래킹 기법을 활용하여 길이 1부터 배열 전체 길이까지의 모든 조합을 순서대로 출력합니다.

알고리즘

시작
    요소의 개수와 요소들을 입력받는다.
    Combi(char a[], int reqLen, int s, int currLen, bool check[], int l)
    함수는 주어진 배열 집합에 대해 가능한 모든 조합을 출력한다.
    //
    여기서,
    char a[]   = 문자 배열
    reqLen     = 요구되는 조합의 길이
    s          = 시작 위치 변수
    currLen    = 현재까지 선택된 길이
    check[]    = 각 원소의 선택 여부를 나타내는 불리언 배열
    l          = 배열의 전체 길이
    //
    함수 본문:
        만약 currLen > reqLen 이면
            반환한다.
        아니면 currLen == reqLen 이면
            새로 생성된 조합을 출력한다.
        만약 s == l 이면
            더 이상 남은 원소가 없으므로 반환한다.
        각 인덱스마다 두 가지 선택지가 있다:
        check[s]를 'true'로 설정한 뒤 currLen과 s를 증가시키며
        재귀적으로 Combi()를 호출하거나,
        check[s]를 'false'로 설정한 뒤 s만 증가시키며
        재귀적으로 Combi()를 호출한다.
끝

핵심 동작 원리

Combi() 함수는 각 원소에 대해 두 가지 경우를 모두 탐색합니다. 하나는 해당 원소를 현재 조합에 포함하는 경우(check[s] = true)이고, 다른 하나는 포함하지 않는 경우(check[s] = false)입니다. 선택된 길이(currLen)가 요구된 길이(reqLen)에 도달하면 true로 표시된 원소들을 출력하고, 한 단계 위로 되돌아가 나머지 경우를 계속 탐색합니다. 이러한 방식은 백트래킹(backtracking)이라 불리며, 조합이나 부분집합을 구하는 문제에서 널리 사용되는 대표적인 기법입니다.

예제 코드

#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;
    Combi(a, reqLen, s + 1, currLen + 1, check, l);
    check[s] = false;
    Combi(a, reqLen, s + 1, currLen, check, l);
}
int main() {
    int i,n;
    bool check[n];
    cout<<"Enter the number of element array have: ";
    cin>>n;
    char a[n];
    cout<<"\n";
    for(i = 0; i < n; i++) {
        cout<<"Enter "<<i+1<<" element: ";
        cin>>a[i];
        check[i] = false;
    }
    for(i = 1; i <= n; i++) {
        cout<<"\nThe all possible combination of length "<<i<<" for the given array set:\n";
        Combi(a, i, 0, 0, check, n);
    }
    return 0;
}

실행 결과

Enter the number of element array have: 5
Enter 1 element: a
Enter 2 element: b
Enter 3 element: c
Enter 4 element: d
Enter 5 element: e
The all possible combination of length 1 for the given array set:
a
b
c
d
e
The all possible combination of length 2 for the given array set:
a b
a c
a d
a e
b c
b d
b e
c d
c e
d e
The all possible combination of length 3 for the given array set:
a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e
The all possible combination of length 4 for the given array set:
a b c d
a b c e
a b d e
a c d e
b c d e
The all possible combination of length 5 for the given array set:
a b c d e