백준 5568 카드 놓기

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

5568번: 카드 놓기

만들 수 있는 정수를 모두 구하는 문제다.

지문에 "이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다."라는 말이 적혀있다.

중복을 없애자.

 

#include <iostream>
using namespace std;

#include <vector>
#include <set>
#include <string>
set<string> ans;

bool visited[11];
void recur(const vector<int>& v, int depth, int K, int now, const string& S){
    if(depth == K){
        ans.insert(S);
    }else{
        for(int i=0; i<v.size(); i++){
            if(visited[i]) continue;
            visited[i] = true;
            string next_S = S + to_string(v[i]);
            recur(v, depth+1, K, i, next_S);
            visited[i] = false;
        }
    }
}
int main(){
    int N, K; cin >> N >> K;
    vector<int> v(N);
    for(int i=0; i<N; i++){
        cin >> v[i];
    }

    recur(v, 0, K, -1, "");
    cout << ans.size();
    return 0;
}

set에 다 때려넣는 것은 중복을 없애는 좋은 방법이다.