중복을 신경쓰지 않기 때문에, 재귀함수 내 for문은 1부터 N까지 돌자. 재귀함수를 M번 호출하면 끝.
참고로, 답을 int형 배열이 아닌 string에 저장하면 입출력 속도가 월등히 빨라진다.
1. int형 배열에 답 저장
#include <bits/stdc++.h>
using namespace std;
int N, M;
int ans[9];
void recur(int cnt) {
if (cnt == M) {
for (int i = 0; i < M; ++i) cout << ans[i] << ' ';
cout << '\n';
return;
}
for (int cur = 1; cur <= N; ++cur) {
ans[cnt] = cur;
recur(cnt + 1);
}
}
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
recur(0);
return 0;
}
2. string에 답 저장
#include <bits/stdc++.h>
using namespace std;
int N, M;
string ans;
void recur(int cnt) {
if (cnt == M) {
ans.back() = '\n';
cout << ans;
return;
}
for (int cur = 1; cur <= N; ++cur) {
ans.push_back(cur + '0');
ans.push_back(' ');
recur(cnt + 1);
ans.pop_back();
ans.pop_back();
}
}
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
recur(0);
return 0;
}
재귀 함수를 돌 때, (이전 재귀함수에서 선택된 수 + 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;
}
그래도 백트래킹이라고 하면, 보통 재귀 함수를 통해 모든 경우의 수를 탐색하는 것을 말한다.
나중에 가지치기(pruning)라는 기법으로 탐색 시간을 줄일 수 있다.
기법이라고 해서 좀 어려워보이는데.. 그냥 조건문을 통해 더 탐색을 할 것인지 결정해주는 거라고 보면 된다.
N과 M 시리즈는 별 거 없다. 백트래킹으로 문제에서 원하는 조건만 잘 지켜주면 해결 가능하다.
코드 재사용을 통해 어떤 조건을 어떻게 바꿔야 하는지 훈련하면 좋을 것 같다.
#include <bits/stdc++.h>
using namespace std;
int N, M;
bool isTrue[9]; // 이미 뽑힌 숫자인지 ?
int ans[9]; // 답 저장
// cnt : 몇 개가 뽑혔는지
void recur(int cnt) {
// 원하는 개수가 다 뽑혔다면 답 출력
if (cnt == M) {
for (int i = 0; i < M; ++i) cout << ans[i] << ' ';
cout << '\n';
return;
}
// 1 ~ N까지 돌면서 안뽑힌 숫자를 뽑고 다음 재귀함수 호출
for (int i = 1; i <= N; ++i) {
if (isTrue[i]) continue;
isTrue[i] = true;
ans[cnt] = i;
recur(cnt + 1);
// 호출이 끝나면 뽑힌 숫자를 놓아준다.
isTrue[i] = false;
}
}
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
recur(0);
return 0;
}
