AcWing 823. 排列-递归
原题链接
困难
作者:
西加加
,
2024-03-04 21:21:06
,
所有人可见
,
阅读 18
用一个bool[]存储对应数字是否被使用过,一个string存储输出;
#include <bits/stdc++.h>
using namespace std;
void arrangements(int n, bool used[], string output = "") {
bool f = false;
for (int i = 0; i < n; i ++) {
if (used[i]) continue;
f = true;
used[i] = true;
arrangements(n, used, output + (char) (48 + i + 1) + ' ');
used[i] = false;
}
if (not f) cout << output << endl;
}
int main() {
int n;
cin >> n;
bool used[n] = {0};
arrangements(n, used);
return 0;
}
一个比较直接的递归逻辑:用一个string保存输出,写一个函数用来查找string是否包含某个char(为了统一性也用递归写),不过最后一个数据超时了,递归的性能确实很差;
#include <bits/stdc++.h>
using namespace std;
bool find(char c, string s, int index = 0) {
if (index == s.size()) return false;
else if (s[index] == c) return true;
else return find(c, s, index + 1);
}
void arrangements(int n, string output = "") {
if (output.size() == 2 * n) {
cout << output << endl;
return;
}
for (int i = 1; i <= n; i ++) {
if (find(48 + i, output)) continue;
arrangements(n, output + (char) (48 + i) + ' ');
}
}
int main() {
int n;
cin >> n;
arrangements(n);
}