BOJ_단계별로 풀어보기(9단계~)/[13단계] 백트래킹
[백준 15650] N과 M (2)
pushback
2022. 3. 11. 16:23
재귀 함수를 돌 때, (이전 재귀함수에서 선택된 수 + 1) ~ N까지 for문을 돌리면 된다.
오름차순으로 출력해야되기 때문에 N과 M (1)에서 사용한 isTrue라는 bool형 배열도 필요없다.
왜 ? 선택되는 순서 자체가 오름차순이기 때문.
#include <bits/stdc++.h>
using namespace std;
int N, M;
int ans[9];
void recur(int prev, int cnt) {
if (cnt == M) {
for (int i = 0; i < M; ++i) cout << ans[i] << ' ';
cout << '\n';
return;
}
for (int cur = prev + 1; cur <= N; ++cur) {
ans[cnt] = i;
recur(cur, cnt + 1);
}
}
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
recur(0, 0);
return 0;
}