15651번: N과 M(3)

[stopmin]

문제: https://www.acmicpc.net/problem/15651

선행문제: 15650번 N과 M(2)
앞서 올렸던 문제 다음 단계의 문제였습니다. 코드 살짝만 바꾸면 바로 풀리는 문제였는데 두 부분만 신경쓰면 됐어요.

• 중복을 허용한다.
• 순서도 상관없다.

따라서 기존에 백트래킹 하기 전에 push_back했던 숫자를 i로 둬도 상관이 없습니다. 다음으로 push할 숫자도 마찬가지로 꼭 start일 필요가 없습니다. 재귀의 시작지점이 아니라 항상 1이어도 상관없게 됩니다. 왜냐하면 순서를 고려하지 않기 때문입니다.

최종 코드

#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<int> combination;

void dfs() {
    if (combination.size() == M) {
        for (int num: combination) {
            cout << num << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 1; i <= N; i++) {
        combination.push_back(i);
        dfs(); // 다음 숫자
        combination.pop_back();
    }
}

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