[백준] C++ 알고리즘 15649번 - N과 M(1)문제

문제

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

15649번: N과 M (1)

소스코드

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n, m;
bool check[9];
vector<int> v;
void go(int index) {
    if (index == m) {
        for (int i = 0; i < m; i++) {
            cout << v[i]<<" ";
        }
        cout << "\n";
    }
    for (int i = 1; i <= n; i++) {
        if (check[i]) continue;
        check[i] = true;
        v.push_back(i);
        go(index + 1);
        v.pop_back();
        check[i] = false;
    }
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    go(0);

}

해설

순서 - N!

선택 - 2^N

순서와 선택 ( 순열과 조합일 경우 ) 재귀를 통해 브루트포스 문제를 해결한다.

우선 이 문제에서는 순서에 따라 경우의 수가 달라진다. 즉 1 2 3 ,2 1 3 선택된 요소는 같지만 순서가 다르므로 다른 경우로 카운트한다.

이를 순열이라고 하며, 순열은 재귀로 구현할 수 있다.