[C++] 백준 10974번 모든 순열

xyzw·2025년 2월 21일
0

algorithm

목록 보기
41/61

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

풀이

백트래킹을 이용하였다.
이미 수열에 포함한 숫자는 다시 넣을 수 없도록 is_used 배열로 중복을 관리해주었다.

코드

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> arr;
vector<bool> is_used;

void backtracking(int len) {
    if(len == n) {
        for(auto& e : arr) {
            cout << e << " ";
        }
        cout << "\n";
        return;
    }
    
    for(int i=1; i<=n; i++) {
        if(is_used[i]) continue;
        
        arr[len] = i;
        is_used[i] = true;
        backtracking(len + 1);
        is_used[i] = false;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
    
    arr.resize(n);
    is_used.resize(n, false);
    
    backtracking(0);
    
    return 0;
}

0개의 댓글