BOJ 15663 : N과 M (9)

이 문제는 n,m 범위가 엄청 작기에 백트래킹으러 풀 수 있다.

 

중복 수열 처리는 STL set의 중복 제거 특징을 이용하여 처리할 수 있다.

 

#include <bits/stdc++.h>
#define sanic ios_base::sync_with_stdio(0);
#define MEM 1002
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll MOD = 1e9+7;
ll n,m;
vector<ll> v,z;
int vis[MEM];
set<vector<ll>> ans;
void bt(int cur, int d){
    if(d==m){
        ans.insert(z);
        return;
    }
    for(int i=0; i<n; i++){
        if(vis[i]) continue;
        vis[i] = 1;
        z.pb(v[i]);
        bt(i,d+1);
        vis[i] = 0;
        z.pop_back();
    }
}
main()
{
    sanic; cin.tie(0);
    cin >> n >> m;
    for(int i=0,q; i<n; i++){
        cin >> q;
        v.pb(q);
    }
    sort(all(v));
    bt(0,0);
    for(auto a : ans){
        for (int i = 0; i < a.size(); i++)
            cout << a[i] << ' ';
        cout << '\n';
    }
}