[자료구조/알고리즘] 재귀 함수를 이용한 부분 집합 생성 알고리즘

#define _CRT_SECURE_NO_WARNINGS                                
#include <iostream> 
#include <vector> 
using namespace std;
vector<int> subset;
int n = 4;
void search(int k)
{
    if (k == n + 1)
    {
        for (int i = 0; i < subset.size(); i++)
            cout << subset[i] << " ";
        cout << endl;
    }
    else
    {
        subset.push_back(k);
        search(k + 1);
        subset.pop_back();
        search(k + 1);
    }
}
int main()
{
    search(1);
}

1부터 n까지의 숫자로 만들 수 있는 부분 집합의 경우의 수를 출력하는 함수다.

마지막 공집합은 빈 줄로 출력이 되기 때문에 실수로 놓치는 것에 주의한다.

 

우리가 부분집합을 손으로 (가지치기하여) 구할 때와 유사한 방식이라고 생각한다.

다만 재귀 알고리즘은 익숙하지 않으면 코드 자체를 보고 실행결과를 예상하기가 힘들다.

 

실행 결과

 

아래는 n = 7 , r = 4 라고 가정하고 7C4의 경우를 모두 출력하는 코드이다.

#include <iostream>
#include <vector>
using namespace std;
vector<int> comb;
int n = 7, r = 4;
void combination(int k)
{
    if (comb.size() == r)
    {
        for (int i = 0; i < comb.size(); i++)
            cout << comb[i] << " ";
        cout << endl;
    }
    else if (k == n + 1) return;
    
    else
    {
        comb.push_back(k);
        combination(k + 1);
        comb.pop_back();
        combination(k + 1);
    }
}
int main()
{
    combination(1);
    return 0;
}

실행 결과

출처: https://doomed-lab.tistory.com/60?category=763786 [둠선생 연구실]