백준 15650번(완전 탐색)

백준 15650번(완전 탐색)

이 문제는 15649번과 유사해보이지만 조금 다른 문제였습니다. 1~N까지 중복없이 M개를 고르고, 고른 수열을 오름차순으로 해줘야 합니다. 입력, 출력 예시를 보면 더욱 쉽게 차이를 이해할 수 있습니다. 이 문제는 prev라는 인자를 추가함으로써 중복을 제거하여 쉽게 해결할 수 있었습니다.

#include <iostream>

using namespace std;

int N, M;

int arr[9];
bool checked[9];

void func(int cnt, int prev) {
	if (cnt == M) {
		for (int i = 0; i < cnt; i++) {
			cout << arr[i] << " ";
		}
		puts("");
		return;
	}
	for (int i = 1; i <= N; i++) {
		if (!checked[i]) {
			if (prev < i) {
				checked[i] = true;
				arr[cnt] = i;
				func(cnt + 1, i);
				checked[i] = false;
			}
		}
	}
}

int main() {
	cin >> N >> M;

	func(0, 0);

	return 0;
}