BOJ 15649 - N과 M (1~12)

N개 중 M개를 뽑아 나열하는 경우의 수 시리즈이다.

 

기본적으로 백트래킹을 이용해서 재귀로 구현함.

 

9~12같은 경우 중복을 제거해줘야 하는데, 이건 set<vector<int>>로 해결하였다.

 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;


void printPicked(vector<int>& picked) {
	for (int n : picked) printf("%d ", n + 1);
	printf("\n");
}

int n, m;
void pick(vector<int>& picked, vector<bool>& isUsed, int k) {
	if (k == m) {
		printPicked(picked);
		return;
	}

	for (int next = 0; next < n; next++) {
		if (!isUsed[next]) {
			picked[k] = next;
			isUsed[next] = true;
			pick(picked, isUsed, k + 1);
			isUsed[next] = false;
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	vector<int> picked(m, 0);
	vector<bool> isUsed(n, false);
	pick(picked, isUsed, 0);
}

 

재귀에 고른 수들 혹은 고른 수들의 인덱스를 저장할 picked 벡터와 여태 고른 수의 개수 k를 전달하는 것이 핵심이다.

 

오름차순의 경우 isUsed가 필요없다.

 

N과 M(9~12)는 다음과 같이 짜 보았다.

#include <vector>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;

int arr[8], n, m;
set<vector<int>> rst;

void pick(vector<int>& picked, vector<bool>& isUsed, int k) {
	if (k == m) {
		rst.insert(picked);
		return;
	}

	for (int i = 0; i < n; i++) {
		if (!isUsed[i]) {
			isUsed[i] = true;
			picked.push_back(arr[i]);
			pick(picked, isUsed, k + 1);
			isUsed[i] = false;
			picked.pop_back();
		}
	}

}

int main() {
	scanf("%d %d", &n, &m);
	vector<int> picked;
	vector<bool> isUsed(n,false);
	for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
	sort(arr, arr + n);

	pick(picked, isUsed, 0);

	for (auto s : rst) {
		for (auto num : s) printf("%d ", num);
		printf("\n");
	}
}