15649: N과 M(1) - 백트래킹

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

 

문제요약

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력하라!

 

난이도

Silver 3

---

풀이 포인트

• 백트래킹

---

REVIEW

 

백트래킹은 곧 dfs다.. 아직 무슨 말인지 잘 와닿지 않는다.

다시 공부해야한다.

---

CODE

// 백트래킹: 뒤로 다시 돌아가서 확인해본다! 역으로 돌아가본다!
// 백트래킹을 곧 dfs라고 할 수 있다!

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

// 거쳐온 경로
vector<int> v;

int visited[10];
int N,M;

// 리프노드에 왔는지 체크를 phase ,단계
void f(int phase){

    if(phase == M){
        for(auto it:v){
            cout << it <<" ";
        }
        cout << '\n';
        return;
    }

    for(int i = 1; i <= N; i++){
        if(visited[i]) continue;

        visited[i] = 1;
        v.push_back(i);
        f(phase + 1);

        // 다시 초기화!
        v.pop_back();
        visited[i] = 0;
    }
}

int main(){
    cin >> N>> M;
    f(0);
}