[BOJ/백준 15649][C++] N과 M (1)

문제

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

백준 15649

 

문제 내용

1~N 까지의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다.

이때 수열을 사전 순으로 증가하는 순서대로 출력해야 한다.

 

문제 풀이

N과 M은 백트래킹의 대표적인 문제이다.

N과 M (1)은 몇 개를 선택했는지만 인자로 넘겨서 종료조건을 체크하면 된다.

 

코드

#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector<bool> used(9, false);
vector<int> result(8, 0);

void back(int cnt) { // 몇개를 선택했는지
    if (cnt == m) {
        for (int i = 0; i < m; i++) {
            cout << result[i] << ' ';
        }
        cout << '\n';
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            used[i] = true;
            result[cnt] = i; // cnt는 0부터 들어간다
            back(cnt + 1);
            used[i] = false;
        }
    }
}

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