[C++] 백준 15654번 N과 M (5)

https://www.acmicpc.net/problem/15654

풀이

중복을 허용하지 않고 N개의 수 중 M개를 고르기 때문에 어떤 수가 이미 수열에 포함되었는지 여부를 저장하는 bool used[] 배열을 만들었고, 이를 이용해 백트래킹을 구현하였다.

코드

#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<int> arr;
bool used[8];

void solution(vector<int>& v) {
    if(v.size() == M) {
        for(auto& e : v) cout << e << ' ';
        cout << '\n';
        return;
    }

    for(int i=0; i<N; i++) {
        if(used[i]) continue;
        
        v.push_back(arr[i]);
        used[i] = true;
        solution(v);
        v.pop_back();
        used[i] = false;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;
    for(int i=0; i<N; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }
    sort(arr.begin(), arr.end());

    vector<int> ans;
    solution(ans);

    return 0;
}