题目描述
给定一个长度为 n 的可包含重复数字的序列,请你求出其所有不重复的全排列。
输入格式
第一行包含整数 n
。
第二行包含 n
个整数。
输出格式
输出所有的不同排列,每种排列占一行。
在确定每种排列的输出顺序时,第一个数较小的先输出,第一个数相同时,第二个数较小的先输出,以此类推。
数据范围1≤n≤9,数组中包含的元素的取值范围 [1,9]
样例
输入样例:
3
1 1 2
输出样例:
1 1 2
1 2 1
2 1 1
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 11;
int num[N];
int path[N];
bool st[N];
int n;
void dfs(int u){
if(u == n){
for(int i = 0; i<n; i++) cout<<path[i]<<" ";
cout<<endl;
return;
}
for(int i = 0; i < n; i ++){//遍历输入的数字
if(!st[i]){
path[u] = num[i];
st[i] = true;
dfs(u+1);
st[i] = false;
while(i+1 < n && num[i] == num[i+1]) {//跳过重复的元素
i++;
}
}
}
}
int main(){
cin>>n;
for(int i = 0; i < n; i++){
cin>>num[i];
}
sort(num, num +n);//排序,以为后面排除重复元素做准备
dfs(0);
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla