DFS를 이용한 조합 만들기

얍문님의 글을 보고 공부했습니다.

https://yabmoons.tistory.com/99

[ 순열과 조합 구현 ] - 재귀를 통한 구현(1 - 조합) (C++)

 

 

이전에 순열을 만드는 방법을 공부했는데

https://tose33.tistory.com/173

DFS를 이용한 순열 만들기

 

이번에는 조합이다.

조합은 순열을 만들줄 알면 쉽다. 코드도 거의 같다.

 

다른점은 조합은 순서가 상관이 없기 때문에 

재귀 호출할때 현재 인덱스를 같이 전해줘서 이전 인덱스의 숫자들은 포함하지 않도록 하는 것이다.

 

n개의 숫자 중 m개의 조합을 뽑을때, m이 작다면 그냥 다중 for문을 구성할수도 있다.

    // 10개 숫자 중, 3개의 조합을 뽑는다
    int n = 10;
    for(int i = 1; i <= n-2; i++)
    {
        for(int j = i + 1; j <= n-1; j++)
        {
            for(int k = j + 1; k <= n; k++)
            {
                cout << i << ' ' << j << ' ' << k << endl;
            }
        }
    }

 

하지만 m이 큰값이라면 dfs나 permutation을 쓰는게 좋다.

다음은 dfs를 이용한 조합을 뽑는 방법이다.

{1,2,3,4,5} 중 3개의 조합을 뽑는 방법이다.

#include <iostream>
using namespace std;

#define MAX 5

int arr[MAX] = {1,2,3,4,5};
bool select[MAX];

void Print() {
    for(int i = 0; i < MAX; i++) {
        if(select[i]) {
            cout << arr[i] << ' ';
        }
    }
    cout << endl;
}

void dfs(int idx, int depth) {
    if(depth == 3) {
        Print();
        return;
    }

    for(int i = idx; i < MAX; i++) {
        if(select[i]) continue;
        select[i] = true;

        dfs(i, depth+1);
        select[i] = false;
    }
}

int main() {
    dfs(0,0);
}

 

코드를 보면 순열을 구하는 코드랑 거의 같지만

dfs가 depth뿐만 아니라 idx도 파라미터로 받는다.

이렇게 idx를 파라미터로 받음으로써 for문을 0부터가 아닌 idx부터 시작해

이미 출력한 조합은 나오지 않도록 한다.