[코드트리 챌린지] 2주차 Backtracking - 순열 만들기 / 거꾸로 순열

백트래킹 못푼게 아쉬워서 다시 진단을 했는데 4문제 풀고 포기하니 100점으로...

https://www.codetree.ai/missions/2/problems/backward-permutation/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드:

#include <bits/stdc++.h>
using namespace std;

int n;
// 선택되었는지 표시하기 위한 배열
bool visit[10];
vector<int> arr;

void Print() {
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
}

void Choose(int cur_num) {
    if (cur_num == n + 1) {
        Print();
        return;
    }


    // 내림차순 출력이므로 n부터 시작
    for (int i = n; i >= 1; i--) {
        // 이미 선택했다면 다시 선택하지 않음
        if (visit[i]) continue;
        visit[i] = true;
        arr.push_back(i);

        Choose(cur_num + 1);

        visit[i] = false;
        arr.pop_back();
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < 10; i++) {
        visit[i] = false;
    }
    Choose(1);
}

visit 배열은 수를 선택했는지 확인하기 위해 쓰이는 배열입니다.

내림차순이므로 for문을 통해 n부터 선택하도록 하고 visit 배열을 확인해 이미 선택 된 수일 경우
선택하지 않고 넘어가도록 합니다.

수를 다시 빼줄 때는 visit 또한 false로 바꿔줍니다.