一、题目
1.原题
有一个考古学家发现一个石碑，
但是很可惜，发现时其已经断成多段，
原地发现n个断口整齐的石碑碎片。
为了破解石碑内容，
考古学家希望有程序能帮忙计算复原后的石碑文字组合数，
你能帮忙吗？
[递归, 字符串, 哈希表]
2.题目理解
有n个碎片（字符可能重复），对这些碎片进行全排列然后输出。
二、思路与代码过程
1.思路
递归 回溯
2.代码过程
①main函数
public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("请输入碎片的块数n：");int n = sc.nextInt();System.out.println("请依次输入碎片上的文字：");sc.nextLine();String[] words = sc.nextLine().split(" ");long factorial = factorial(n);System.out.println("当前碎片有"+factorial+"种排列方式");Arrays.sort(words); // 排序以处理重复元素ArrayList<String> reStrings = new ArrayList<>();StringBuilder reString = new StringBuilder();boolean[] used = new boolean[n];ArrayList<String> ReStrings = BackTrack(reStrings, reString, words, used);for (String s : ReStrings) {System.out.println(s);}}②数量计算（写来好玩的）
//计算阶乘public static long factorial(int n) {return LongStream.rangeClosed(1, n).reduce(1, (a, b) -> a * b);}
③BackTrack函数
private static ArrayList<String> BackTrack(ArrayList<String> reStrings, StringBuilder reString,String[] words, boolean[] used) {if (reString.toString().split(" ").length == words.length) {reStrings.add(reString.toString().trim()); // 去掉末尾的空格} else {for (int i = 0; i < words.length; i++) {if (used[i]) continue;if (i > 0 && words[i].equals(words[i - 1]) && !used[i - 1]) continue;reString.append(words[i]).append(" ");used[i] = true;BackTrack(reStrings, reString, words, used);// 回溯reString.setLength(reString.length() - words[i].length() - 1); // 1 for spaceused[i] = false;}}return reStrings;}三、运行结果
1.运行截图
2.带数据分析运行结果
请输入碎片的块数n：
3
请依次输入碎片上的文字：
i o u
当前碎片有6种排列方式
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：false
组合中，当前i为：i
组合后，当前reString为：i
=======进入回溯啦======
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：true
当前i：i被用过啦！
当前i为：1，word为：o,使用状况为：false
组合中，当前i为：o
组合后，当前reString为：i o
=======进入回溯啦======
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：true
当前i：i被用过啦！
当前i为：1，word为：o,使用状况为：true
当前i：o被用过啦！
当前i为：2，word为：u,使用状况为：false
组合中，当前i为：u
组合后，当前reString为：i o u
=======进入回溯啦======
-----------------BackTrack Start------------------
完成了一条组合：i o u
当前reStrings为：[i o u]
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：i o
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：i
当前i为：2，word为：u,使用状况为：false
组合中，当前i为：u
组合后，当前reString为：i u
=======进入回溯啦======
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：true
当前i：i被用过啦！
当前i为：1，word为：o,使用状况为：false
组合中，当前i为：o
组合后，当前reString为：i u o
=======进入回溯啦======
-----------------BackTrack Start------------------
完成了一条组合：i u o
当前reStrings为：[i o u, i u o]
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：i u
当前i为：2，word为：u,使用状况为：true
当前i：u被用过啦！
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：i
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：
当前i为：1，word为：o,使用状况为：false
组合中，当前i为：o
组合后，当前reString为：o
=======进入回溯啦======
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：false
组合中，当前i为：i
组合后，当前reString为：o i
=======进入回溯啦======
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：true
当前i：i被用过啦！
当前i为：1，word为：o,使用状况为：true
当前i：o被用过啦！
当前i为：2，word为：u,使用状况为：false
组合中，当前i为：u
组合后，当前reString为：o i u
=======进入回溯啦======
-----------------BackTrack Start------------------
完成了一条组合：o i u
当前reStrings为：[i o u, i u o, o i u]
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：o i
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：o
当前i为：1，word为：o,使用状况为：true
当前i：o被用过啦！
当前i为：2，word为：u,使用状况为：false
组合中，当前i为：u
组合后，当前reString为：o u
=======进入回溯啦======
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：false
组合中，当前i为：i
组合后，当前reString为：o u i
=======进入回溯啦======
-----------------BackTrack Start------------------
完成了一条组合：o u i
当前reStrings为：[i o u, i u o, o i u, o u i]
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：o u
当前i为：1，word为：o,使用状况为：true
当前i：o被用过啦！
当前i为：2，word为：u,使用状况为：true
当前i：u被用过啦！
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：o
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：
当前i为：2，word为：u,使用状况为：false
组合中，当前i为：u
组合后，当前reString为：u
=======进入回溯啦======
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：false
组合中，当前i为：i
组合后，当前reString为：u i
=======进入回溯啦======
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：true
当前i：i被用过啦！
当前i为：1，word为：o,使用状况为：false
组合中，当前i为：o
组合后，当前reString为：u i o
=======进入回溯啦======
-----------------BackTrack Start------------------
完成了一条组合：u i o
当前reStrings为：[i o u, i u o, o i u, o u i, u i o]
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：u i
当前i为：2，word为：u,使用状况为：true
当前i：u被用过啦！
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：u
当前i为：1，word为：o,使用状况为：false
组合中，当前i为：o
组合后，当前reString为：u o
=======进入回溯啦======
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：false
组合中，当前i为：i
组合后，当前reString为：u o i
=======进入回溯啦======
-----------------BackTrack Start------------------
完成了一条组合：u o i
当前reStrings为：[i o u, i u o, o i u, o u i, u i o, u o i]
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：u o
当前i为：1，word为：o,使用状况为：true
当前i：o被用过啦！
当前i为：2，word为：u,使用状况为：true
当前i：u被用过啦！
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：u
当前i为：2，word为：u,使用状况为：true
当前i：u被用过啦！
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：
-----------------BackTrack End------------------
i o u
i u o
o i u
o u i
u i o
u o i
3.带数据分析完整代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.LongStream;public class test36 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("请输入碎片的块数n：");int n = sc.nextInt();System.out.println("请依次输入碎片上的文字：");sc.nextLine();String[] words = sc.nextLine().split(" ");long factorial = factorial(n);System.out.println("当前碎片有"+factorial+"种排列方式");Arrays.sort(words); // 排序以处理重复元素ArrayList<String> reStrings = new ArrayList<>();StringBuilder reString = new StringBuilder();boolean[] used = new boolean[n];ArrayList<String> ReStrings = BackTrack(reStrings, reString, words, used);for (String s : ReStrings) {System.out.println(s);}}//计算阶乘public static long factorial(int n) {return LongStream.rangeClosed(1, n).reduce(1, (a, b) -> a * b);}private static ArrayList<String> BackTrack(ArrayList<String> reStrings, StringBuilder reString,String[] words, boolean[] used) {System.out.println("-----------------BackTrack Start------------------");if (reString.toString().split(" ").length == words.length) {System.out.println("完成了一条组合："+reString.toString().trim());//reStrings.add(reString.toString().trim()); // 去掉末尾的空格System.out.println("当前reStrings为：" +reStrings);//} else {System.out.println("正在组合哦！");//for (int i = 0; i < words.length; i++) {System.out.println("当前i为："+i+"，word为："+words[i]+",使用状况为："+used[i]);//if (used[i]){System.out.println("当前i："+words[i]+"被用过啦！");//continue;}if (i > 0 && words[i].equals(words[i - 1]) && !used[i - 1]){//处理重复System.out.println("当前i为："+words[i]+"和前面的重复啦，跳过哦！");continue;}System.out.println("组合中，当前i为："+words[i]);//reString.append(words[i]).append(" ");System.out.println("组合后，当前reString为："+reString);//used[i] = true;System.out.println("=======进入回溯啦======");BackTrack(reStrings, reString, words, used);System.out.println("=======回溯完成啦======");// 回溯reString.setLength(reString.length() - words[i].length() - 1); // 1 for spaceSystem.out.println("撤销后当前的reString为："+reString);used[i] = false;}}System.out.println("-----------------BackTrack End------------------");return reStrings;}
}