题目描述

给定一个长度为 n 的可包含重复数字的序列，请你求出其所有不重复的全排列。

样例

输入样例：
3
1 1 2

输出样例：
1 1 2
1 2 1
2 1 1

数据范围

1≤n≤9,
数组中包含的元素的取值范围 [1,9]

算法1

(暴力枚举dfs)

C++ 代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int n;
int state[11]={0}; //用于标记第i个位置上选取的数字是多少,即存储方案
int visited[11]={0};//用于标记a中第i个元素是否已经被选择,排列要求数字不重复
void dfs(int u,int* a)
{
    if(u>n)
    {
        for(int i=1;i<=n;i++)
            printf("%d ",state[i]);
        printf("\n");
        return;
    }
    for(int i=0;i<n;i++)
    {
        if(visited[i])                  //剪枝操作1
            continue;
        if(i>0&&a[i-1]==a[i]&&visited[i-1]==0)  //剪树操作2
            continue;
        visited[i]=1;                   
        state[u]=a[i];
        dfs(u+1,a);
        visited[i]=0;

    }
}
int main()
{
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    dfs(1,a);
}