백준 15650 - N 과 M (2) - 순열
백준 15650 - N 과 M (2) - 순열 Post not found: algorithm/baekjoon/경우의수/15649-N과M-cpp Post not found: algorithm/baekjoon/경우의수/15650-N과M-cpp 링크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;}