백준 15650: N과 M (2)

문제 요약

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

문제 분류

• 백트래킹

문제 풀이

기존 [C++] 백준 15649: N과 M (1)과 비슷한 문제인데, 이번에는 오름차순으로 나열할 것을 조건으로 추가하였다.

이에 현재의 정점이 이전의 정점보다 큰 경우에만 ary배열에 추가해주었다.

풀이 코드

#include <stdio.h>
#include <iostream>

using namespace std;

bool visited[9];
int ary[9], n, m;

void dfs(int cnt)
{
    if (cnt >= m) {
        for (int i = 0; i < m; i++)
            printf("%d ", ary[i]);
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            if (cnt == 0 || ary[cnt - 1] < i) {
                visited[i] = true;
                ary[cnt] = i;
                dfs(cnt + 1);
                visited[i] = false;
            }
        }
    }
}

int main() {
    cin >> n >> m;
    dfs(0);
    return 0;
}