백준 10974 모든 순열

문제 링크 : https://www.acmicpc.net/problem/10974

n이 작아서 재귀를 이용한 완전탐색으로 풀었다.

1. n을 입력받고,  pair<int, bool>가 들어갈 벡터 v를 선언하고 1~n까지 총 n개의 수를 벡터에 넣어주었다.

( pair의 first : 1~n까지의 정수 / pair의 second : 해당 정수를 선택했는지 여부 )

2. 재귀를 이용하여 완전탐색을 하였다.

for문으로 벡터v를 훑으면서 선택하지 않은 수가 있다면 선택하여 picked 벡터에 추가.

n개의 수를 모두 선택하였다면 벡터 picked 출력하고 함수 종료.

아래는 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;
 
int n;
vector<pair<int, bool>> v;
vector<int> picked;
 
void pick(int toPick) {
    if (toPick == 0) {
        for (int i = 0; i < picked.size(); i++) {
            cout << picked[i] << " ";
        }
        cout << "\n";
        return;
    }
 
    for (int i = 0; i < n; i++) {
        if (v[i].second) continue;
 
        v[i].second = true;
        picked.push_back(v[i].first);
        pick(toPick - 1);
        v[i].second = false;
        picked.pop_back();
    }
}
 
int main()
{
    cin >> n;
 
    for(int i = 1; i <= n; i++) {
        v.push_back(make_pair(i, false));
    }
 
    pick(n);
}