[BOJ/C++] 15651번 : N과 M(3)

우선 나는 N과 M 시리즈를 다 풀면서 백트레킹을 마스터 해보겠다.. 근데 이문제는 너무 간단해서 왜 3번인지 모르겠다 차라리 얘를 1번으로 두지 일단 문제를 봐보자

우선 이번에는, 1부터 N까지 M개를 고르는데 같은 수를 여러번 골라도되고 오름차순도 아니다. 즉, 4 2 가 들어오면 1 1, 1 2, 1 3, 1 4, 2 1, .... 이런식으로 다 출력하면 된다. 이를 고려해서 코드를 짜보자

#include <iostream>
using namespace std;

int N, M;
int arr[9];

void backtrack(int depth) {
    if (depth == M) { 
        for (int i = 0; i < M; i++) {
            cout << arr[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 1; i <= N; i++) { 
        arr[depth] = i; 
        backtrack(depth + 1);  
    }
}

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

우선, 어차피 다 출력하니까 방문 여부도 볼 필요없어서 visited배열을 제거했다. 당연히 인자도 하나만 있으면 된다 그냥 증가만 시키면 되니까 ! 아주 단순하게 풀렸다 굿.