[알고리즘] 15649 / N과 M(1) / C++

브루트포스 문제는

- 재귀

- 순열 

- 비트마스크

를 사용해서 풀 수 있는데 순열, 비트마스크로 푸는 방법 모두 재귀를 쓰는 방법으로 만들 수 있기 때문에

재귀가 가장 중요하다.

 

재귀를 사용한 브루트포스 문제는 

- 순서

- 선택

문제를 풀 수 있다.

 

❓ 대표적으로 15649 백준 N과 M 문제가 있다.

▶ 1부터 N까지 자연수 중에 중복 없이 M개를 고른 수열을 모두 구하는 문제이다.

    - '중복없이' 조건이 있기 때문에 중복체크를 해줄(기억해 줄) 배열이 필요하다.

void make_seq(int index, int n, int m) {
	if (index == m) {
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (c[i]) continue;
		c[i] = true;
		a[index] = i;
		make_seq(index + 1, n, m);
		c[i] = false;
	}
}