백준 15650번 N과 M (2) 문제풀이(C++)

백준 15649번 n과 m (2)

아이디어

부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 -> visited로 방문 처리 및 인덱스 설정 중요

고른 수열은 오름차순이어야 한다 -> 1부터 시작

문제풀이

n과 m(1)의 코드에서 i의 시작값을 설정해주면서 중복을 없애주었다.

#include <iostream>
#define MAX 9
using namespace std;
int n, m;
int arr[MAX] = { 0, };
bool visited[MAX] = { 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++){
        if (!visited[i])
        {
            visited[i] = true;
            arr[cnt] = i;
            dfs(i + 1, cnt + 1);
            visited[i] = false;
        }
    }
}
int main() {
    cin >> n >> m;
    dfs(1, 0);
}