AcWing 94. 递归实现排列型枚举
原题链接
简单
作者:
YouSansan
,
2023-11-14 20:10:40
,
所有人可见
,
阅读 54
有重复数的全排列
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
// 假设要排的数不会超过20个
const int N = 20;
int n;
int st[N], a[N], used[N];
void dfs(int u) {
if (u == n) {
for (int i = 0; i < n; i ++ ) {
printf("%d ", st[i]);
}
puts("");
return;
}
for (int i = 0; i < n; i ++ ) {
if (used[i] || (i > 0 && a[i] == a[i - 1] && !used[i - 1])) continue;
st[u] = a[i];
used[i] = 1;
dfs(u + 1);
st[u] = 0;
used[i] = 0;
}
}
void quick_sort(int a[], int l, int r) {
if (l >= r) return;
int x = a[l], i = l - 1, j = r + 1;
while (i < j) {
while (1) {
i ++ ;
if (!(a[i] < x)) break;
}
while (1) {
j -- ;
if (!(a[j] > x)) break;
}
if (i < j) std::swap(a[i], a[j]);
}
quick_sort(a, l, j);
quick_sort(a, j + 1, r);
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
quick_sort(a, 0, n - 1);
dfs(0);
system("pause");
return 0;
}