AcWing 1537. 递归实现重复值排列II
原题链接
简单
作者:
orange0912
,
2021-01-05 15:19:15
,
所有人可见
,
阅读 445
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=20;
int a[N],nums[N];//记录当前选择的下标
bool st[N];//记录递归搜索树搜索到某个节点时之前搜索过的路径
int n;
void dfs(int u)
{
if(u==n)//本体从0下标开始存储数据
{
for(int i=0;i<n;i++)
printf("%d ",nums[i]); //输出第i个选择的数
puts("");
return;
}
for(int i=0;i<n;i++)
{
if(st[i]==false)//i这个数之前尚未访问过
{
nums[u]=a[i];
st[i]=true;
dfs(u+1);
st[i]=false;
//用完a[i]这个数后,需要把和它相同的数都跳过
while(i+1<n&&a[i+1]==a[i])
i++;
}
}
}
int main( ) {
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
dfs(0);//从第一层开始考虑第一个位置的数
return 0;
}