[BOJ]15650 N과 M (2) - 조합

• sol : 백트래킹 재귀 DFS
• 조합(Combination) : $nCm$의 코드식 구현
  • $nCr = n! / ((n - r)! * r!)$
  • 앞에 나온 수 < 뒤의 나온 수
    • 이전 단계의 수를 의미하는 인자 하나(num)를 추가해 이전 단계의 수 이상의 수만 받아들이도록 사용
• 고찰
  • visited가 없다면 1...1 to N...N의 수를 순환하는 수열
  • visited를 통해 방문된 수를 선점
    • 수가 오름차순으로 들어오므로, 당연히 오름차순 수열이 된다.
  • 방문이 종료되었다면, visited를 통해 선점 해제
    • 해당 수보다 작지만 앞선 수보다 큰 수가 들어갈 수 있도록

#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> vec(9, 0);
vector<bool> visited(9, false);
void DFS(int depth, int num){
    if(depth == M){
        for(int i = 0; i < M; ++i){
            cout << vec[i] << ' ';
        }
        cout << '\n';
        return;
    }
    for(int i = num; i <= N; ++i){
        if(!visited[i]){
            visited[i] = true;
            vec[depth] = i;
            DFS(depth+1, i+1);
            visited[i] = false;
        }
    }
}
int main(){
    //1 to N 중복 비허용 M개
    //오름차순
    cin >> N >> M;
    DFS(0, 1);
    return 0;
}

• sol2 : NextPermutation
  • 벡터 내 순열을 쉽게 구해주는 next_permutation() 활용
    • #include <algorihtm> 헤더 필수

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int N, M; // N : 전체 원소의 개수, M : 정렬할 원소의 개수.
vector<int> arr;
vector<int> combination;
int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		arr.push_back(i);
	sort(arr.begin(), arr.end());
	for (int i = 0; i < N; i++) {
		if (i < N-M) combination.push_back(0);
		else combination.push_back(1);
	}
	do {
		for (int i = 0; i < arr.size(); i++) {
			if (combination[i] == 1) 
				cout << arr[i] << " ";
		}
		cout << '\n';
	} while (next_permutation(combination.begin(), combination.end()));
}