[Silver 3] 15652번 N과 M (4)

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

15652번: N과 M (4)

 

이 문제는 DFS를 통한 백트레킹을 통해 해결할 수 있다.

 

알고리즘은 다음과 같다.

N과 M (2)와 다르게 2자리를 출력할 때 같은 숫자를 출력해야한다.

따라서 dfs의 visited 배열을 빼고 순회하면 같은 숫자인 수열도 뽑을 수 있다.

 

#include <iostream>
using namespace std;

int N, M;
int arr[9] = { 0, };
int visited[9] = { 0, };

void dfs(int num, int cnt)
{
    if (cnt == M)
    {
        for (int i = 0; i < M; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for (int i = num; i <= N; i++)
    {
        arr[cnt] = i;
        dfs(i, cnt + 1);
    }
}

int main() {
    cin >> N >> M;
    dfs(1, 0);
}