[백준 15652] N과 M(4) - C++ / 백트래킹, 재귀 알고리즘

문제

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

15652번: N과 M (4)

나의 코드

#include <iostream>
#include <vector>
#define MAX 8
 
using namespace std;
 
int arr[MAX];  //수열 숫자
vector<int> vec;  //수열
bool visited[MAX][MAX];  //각 cnt단계의 방문여부 - 0으로 초기화됨
int cnt, n, m;
 
void Print() {
    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i] << ' ';
    }
    cout << '\n';
}
 
void DFS(int cnt, int s) {
    if (cnt == m) {
        Print();
        return;
    }
 
    for (int i = s; i < n; i++) {
        if (visited[cnt][i]) continue;
        visited[cnt][i] = true;
        vec.push_back(arr[i]);
        DFS(cnt + 1, arr[i] - 1);
        visited[cnt][i] = false;
        vec.pop_back();
    }
}
 
int main(void) {
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        arr[i] = i + 1;
    }
 
    DFS(0, 0);
}

여기서 핵심은 int s이다.

그 이전 단계의 숫자부터 탐색을 시작하면 되므로

예를 들어)

1 -> 1 -> 1 

2 -> 2 -> 2 ( cnt = 1인 단계에서 그 이전 단계 숫자부터 시작해서 2이고, cnt = 2인 단계에서 그 이전 단계 숫자가 2이므로 2부터 시작해서 탐색한다!!)