백준 15649 N과 M(1) / C++

문제 : 링크텍스트

풀이 point

전형적인 백트래킹 문제
1->2->3->4
1->2->4->3(2까지 돌아온 후 다음 값을 진행한 것)
1->3->2->4(2를 선택할 때 1이 이미 선택됐으므로 2를 선택함)
1->3->4->2(visit 배열을 통해 관리)

풀이 순서

백트래킹 구현
숫자가 1부터 시작하기 떄문에 1인덱스 활용

코드

//백준 15649, N과 M(1)

#include <iostream>
#include <vector>
#include <queue>

bool visit[9];
int arr[9];

int N, M;

void solve(int k){
    if(k == M){
        for(int i{0}; i<M; ++i)
            std::cout << arr[i] << ' ';
        std::cout << '\n';    
        return;
    }
    for(int i{1}; i<=N; ++i){
        if(!visit[i]){
            visit[i] = true;
            arr[k] = i;
            solve(k+1);
            visit[i] = false;
        }
    }
}

int main(){
    
    std::cin >> N >> M;
    solve(0);
    
    return 0;
}