[백준] N과 M (2) - 조합

 

조합.

depth를 증가 시키는 것과, start를 하나 더 늘리는 것이 관건이다.

한 재귀함수가 호출되면, depth가 고정되어 있는 채로, start와 관련된 i 인덱스가 바뀌면서 다음 조합의 수를 채운다.

#include <cstdio>
int N, M;
int a[9];

void combination(int depth, int start){
    if (depth == M){
        for (int i=0; i<M; ++i) printf("%d ", a[i]);
        puts("");
        return;
    }

    for (int i=start; i<=N; ++i){
        a[depth] = i;
        combination(depth + 1, i + 1);
    }
}

int main() {
    scanf("%d %d", &N, &M);
    combination(0, 1);
    return 0;
}

 

또는 stack (vector)을 이용해서 하는 방법이 있다.

stack이 M개 만큼 꽉차면 출력한다.

 

#include <cstdio>
#include <vector>
using namespace std;
typedef vector<int> vi;
int n, m;

void printlnVector(vi & v){
    for (int i=0; i<v.size(); ++i) printf("%d ", v[i]);
    printf("\n");
}

void dfs(vi & v){
    if (v.size() == m){
        printlnVector(v);
        return;
    }
    int smallest = v.empty() ? 0 : v.back();
    for (int i=smallest + 1; i<=n; ++i){
        v.emplace_back(i);
        dfs(v);
        v.pop_back();
    }
}

int main() {
    scanf("%d %d", &n, &m);
    vi vec;
    dfs(vec);
    return 0;
}