[BOJ/백준][Silver2] 15664 : N과 M (10) (C++)

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

15664번: N과 M (10)

 

 

[난이도] Silver2
[유형] 백트래킹

[풀이]
오름차순으로 출력해야 하기 때문에 정렬 후에 백트래킹을 해주면 됩니다.
중복 제거를 위해 set을 이용하였습니다.

 

#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
int N,M,a[8];
set<vector<int>> st;
vector<int> ans;
void sol(int n){
    if(n==N){
        if(ans.size()==M) {
            if(st.find(ans) == st.end()){
                st.insert(ans);
                for(auto k : ans) printf("%d ",k);
                puts("");
            }
        }
        return;
    }
    ans.push_back(a[n]);
    sol(n+1);
    ans.pop_back();
    sol(n+1);
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    sort(a,a+N);
    sol(0);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/15664.cpp