[백준] 15651 N과 M (4) - 중복조합

15650 N과 M (2)를 풀었다면, 정말 거저 먹는 문제이다!

시작하는 부분만 한 단계 낮추어, 중복이 가능하게 하면된다.

이것 역시 stack버전과, 그냥 배열을 쓴 버전 두가지를 참고하시라.

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

void repeated_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;
        repeated_combination(depth + 1, i);
    }
}

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

 

 

stack은 vector를 이용해 구현을 했다.

#include <iostream>
#include <vector>

using namespace std;
int N, M;

ostream & operator<< (ostream & os, const vector<int> & rhs) {
    for (int i=0; i<rhs.size(); ++i)
        os << rhs[i] << " ";
    return os;
}

void repeated_combination(vector<int> & v, int start){
    if (v.size() == M){
        cout << v << '\n';
        return;
    }
    for (int i=start; i<=N; ++i){
        v.emplace_back(i);
        repeated_combination(v, i);
        v.pop_back();
    }
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M;
    vector<int> v;
    repeated_combination(v, 1);
    return 0;
}