자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
<algorithm>
헤더의 next_permutation()
함수를 쓰면 간단하게 풀 수 있는 문제지만, 만일 STL을 사용할 수 없는 경우라면 이 문제를 어떻게 풀 수 있을지 생각해보자.idx
번 위치에 1부터 8까지의 숫자를 넣고 다음 재귀를 돌리고 다시 빼는 과정을 반복한다.#include <iostream>
int n, m, c[9], a[9];
void solve(int idx) {
// m개를 선택했다면, 결과를 출력한다.
if (idx == m) {
for (int i = 0; i < m; ++i) printf("%d ", a[i]);
printf("\n");
return;
}
// 1부터 n까지의 수를 '고정', '실행', '해제'한다.
for (int i = 1; i <= n; ++i) {
if (c[i]) continue;
a[idx] = i;
c[i] = 1;
solve(idx + 1);
c[i] = 0;
a[idx] = 0;
}
}
int main() {
scanf("%d %d", &n, &m);
solve(0);
}