[ C++ / 백준 15663번 ] N과 M (9)

 

 

앞의 문제들과 똑같이 풀이를 한다. 그러나 중복되는 수열을 여러 번 출력하면 안된다. 

 

따라서 set 을 사용하여 풀이했다. 처음에는 unordered_set 을 사용해야 하나 하고 생각했었지만 순회를 전부 돌기 때문에 상관이 없다는 것을 이내 깨달았다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>


using namespace std;

vector<int> v;
vector<int> input_v(10);

set<vector<int>> s;

bool visited[10] = { false };

int N, M;

void dfs(int input)
{

    if (input == M)
    {
        s.insert(v);
        /*
        for (auto i : v)
        {
            cout << i << " ";
            
        }
        cout << '\n';
        */
        return;
    }
    else
    {
        for (int i = 0; i < input_v.size(); i++)
        {
            if (!visited[i])
            {
               //if (!v.empty() && input_v[i] < v.back()) continue;
               
                visited[i] = true;
                
                v.push_back(input_v[i]);

                dfs(input + 1);

                visited[i] = false;
                v.pop_back();



            }
        }
    }
    
        


}

int main() {

    cin >> N >> M;

    input_v.resize(N);
    
    for (int i = 0; i < N; i++)
        cin >> input_v[i];


    sort(input_v.begin(), input_v.end());

    //input_v.erase(unique(input_v.begin(), input_v.end()), input_v.end());
    //for (auto i : input_v)
    //    cout << i << " ";
    //cout << endl;
   
    dfs(0);
 
    for (auto i : s)
    {
        for (auto j : i)
        {
            cout << j << " ";
        }
        cout << '\n';
    }
        

    return 0;
}