[BOJ]15666 N과 M (12)

• sol1 : 백트래킹 재귀 DFS
  • 순열의 중복 저장 / 중복된 순열의 출력을 막는다.
  • 이를 위해 중복을 제거하는 set에 저장 후 출력

#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> input;
vector<int> vec(9);
set<vector<int>> ans;
//중복되는 수열 출력 불가
//사전 순으로 증가
void DFS(int depth){
    if(depth == M){
        vector<int> anstmp;
        for(int i = 0; i < M; ++i)
            anstmp.push_back(vec[i]);
        ans.insert(anstmp);
        return;
    }
    for(int i = 0; i < N; ++i){
        vec[depth] = input[i];
        DFS(depth+1);
    }
}
int main(){
    cin >> N >> M;
    for(int i = 0; i < N; ++i){
        int tmp;
        cin >> tmp;
        input.push_back(tmp);
    }
    sort(input.begin(), input.end());
    DFS(0);
    for(auto s : ans){
        for(auto i : s){
            cout << i << ' ';
        }
        cout << '\n';
    }
    return 0;
}

• sol2 : more efficient
  • 순열의 앞부분은 중복되지 않음
  • 뒤에 나오는 순열의 중복만 막으면 더 효울적인 코드 구성 가능

#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> input;
vector<int> vec(9);
void DFS(int depth, int num){
    if(depth == M){
        for (int i = 0; i < M; ++i) {
          cout << vec[i] << ' ';
        }
        cout << '\n';
        return;
    }
    int tmp = 0;
    for(int i = num; i < N; ++i){
        if(tmp != input[i]){
            vec[depth] = input[i];
            tmp = vec[depth];
            DFS(depth+1, i);
        }
    }
}
int main(){
    cin >> N >> M;
    for(int i = 0; i < N; ++i){
        int tmp;
        cin >> tmp;
        input.push_back(tmp);
    }
    sort(input.begin(), input.end());
    DFS(0, 0);
    return 0;
}