백준 15650 - N 과 M (2) - 순열

• 백준 15649 - N 과 M (1) - 순열
• 백준 15650 - N 과 M (2) - 순열

링크

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

문제 풀이

주어진 N 개에서 M 개를 뽑는 경우의 수를 다루는 조합 문제

• 백트레킹 을 이용해 만들 수 있는 모든 경우의 수를 만들어 줬다.
• 다만, 조합은 순서와 상관 없이 뽑은 상태가 같으면 같은 Case 로 분류가 된다.
• 때문에 현재 뽑은 위치(idx) 에서 앞에 있는 것들만 뽑게 하면 같은 경우의 수가 나오는 것을 방지할 수 있다.

전체 소스 코드

#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;

vector<int> v;
vector<bool> check;

// idx : 수열 탐색 현재 시작 위치를 알려주기 위한 변수
// depth : 재귀 문이 몇번 호출 됐는지 확인하기 위한 변수
// n : 수열 탐색의 마지막 위치를 확인하기 위한 값
// m : 재귀 문을 최대 호출할 수 있는 횟수

void nCr(int idx, int depth, int n, int m) {
    if (depth == m) {
        for (int value : v) {
            cout << value << " ";
        }
        cout << endl;
        return;
    }

    for (int i = idx; i < n; i++) {
        if (check[i] == true) {
            continue;
        }
        check[i] = true;
        v[depth] = i + 1;
        nCr(i + 1, depth + 1, n, m);
        check[i] = false;
    }
}

int main(void) {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;

    v = vector<int>(m);
    check = vector<bool>(n);

    nCr(0, 0, n, m);

    return 0;
}