题目描述

有一个考古学家发现一个石碑，但是很可惜，发现时其已经断成多段，原地发现n个断口整齐的石碑碎片。为了破解石碑内容，考古学家希望有程序能帮忙计算复原后的石碑文字组合数，你能帮忙吗？

输入描述

第一行输入n，n表示石碑碎片的个数。

第二行依次输入石碑碎片上的文字内容s，共有n组。

输出描述

输出石碑文字的组合（按照升序排列），行末无多余空格。

备注

如果存在石碑碎片内容完全相同，则由于碎片间的顺序变换不影响复原后的碑文内容，即相同碎片间的位置变换不影响组合。

用例1

输入

3
a b c

Copy

输出

abc
acb
bac
bca
cab
cba

Copy

说明

当石碑碎片上的内容为“a”，“b”，“c”时，则组合有“abc”，“acb”，“bac”，“bca”，“cab”，“cba”

用例2

输入

3
a b a

Copy

输出

aab
aba
baa

Copy

说明

当石碑碎片上的内容为“a”，“b”，“a”时，则可能的组合有“aab”，“aba”，“baa”

用例3

输入

3
a b ab

Copy

输出

aabb
abab
abba
baab
baba

Copy

说明

当石碑碎片上的内容为“a”，“b”，“ab”时，则可能的组合有“aabb”，“abab”，“abba”，“baab”，“baba”

和明显用全排列，结果去重然后排序。

    import java.util.*;
    import java.io.*;

    public class Main{
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.valueOf(br.readLine());
            String[] s = br.readLine().split(" ");
            Set<String> ans=new HashSet<>();
            dfs(s,0,new ArrayList<String>(),ans);
            ArrayList<String> list=new ArrayList<>(ans);
            Collections.sort(list);
            for(String i:list){
                System.out.println(i);
            }
        }

        public static void dfs(String[] s,int i,List<String> path,Set<String> ans){
            if(i==s.length){
                StringJoiner sj=new StringJoiner("");
                for(String p:path) sj.add(p);
                ans.add(sj.toString());
                return;
            }

            Set<String> visited=new HashSet<>();
            for(int k=i;k<s.length;k++){
                if(visited.contains(s[k])) continue;
                visited.add(s[k]);

                swap(s,i,k);
                path.add(s[i]);
                dfs(s,i+1,path,ans);
                path.remove(path.size()-1);
                swap(s,i,k);

            }
        }

        public static void swap(String[] s,int i,int j){
            String t=s[i];
            s[i]=s[j];
            s[j]=t;
        }
    }