BOJ | 15649 N과 M(1)

| Link

BOJ 15649

| Problem

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

---

재귀 이용
check 배열로 해당 숫자가 사용되었는지 확인하기
size가 m과 같으면 출력
1부터 n까지의 수를 재귀로 돌리면서 탐색

| Code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;

bool check[9];
int n, m;
vector<int> seq;

void func(int size) {
	if (size == m)
	{
		for (int i:seq)
			printf("%d ", i);
		printf("\n");
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (!check[i]) {
			check[i] = true;
			seq.push_back(i);
			func(size + 1);
			seq.pop_back();
			check[i] = false;
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	func(0);
	return 0;
}

| Result