백준 15649 N과 M (1)

앞선 재귀 문제들처럼 vector에 원소를 넣을지 말지를 선택하는 선택하는 문제다.

vector에 넣은 원소의 개수가 주어진 수와 같을 때 재귀를 종료시키면 된다.

중복해서 뽑지 않도록 check해주는 것만 조심하면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
 
int n, m;
vector<int> v;
 
bool check(int num) {
    for (int i = 0; i < v.size(); i++) {
        if (v[i] == num)return true;
    }
    return false;
}
 
void solve() {
    //뽑아야 할 개수만큼 뽑고 나면 출력한다.
    if (v.size() == m) {
        for (auto x : v) {
            printf("%d ", x);
        }
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; i++) {
        //중복되면 안되므로 이미 들어있는 원소인지 확인한다.
        if (check(i)) continue;
        v.push_back(i);
        solve();
        v.pop_back();
    }
}
 
int main(int argc, char** argv) {
    cin >> n >> m;
 
    solve();
 
    return 0;
}