华为OD机试 - 考古问题 - 回溯、全排列问题（Java 2024 C卷 200分）

在这里插入图片描述

华为OD机试 2024C卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

考古问题，假设以前的石碑被打碎成了很多块，每块上面都有一个或若干个字符，请你写个程序来把之前石碑上文字可能的组合全部写出来，按升序进行排列。

二、输入描述

若干个字符。

三、输出描述

把之前石碑上文字可能的组合全部写出来，按升序进行排列。

1、输入

3
a b c

2、输出

abc
acb
bac
bca
cab
cba

四、解题思路

把之前石碑上文字可能的组合全部写出来，按升序进行排列；
定义可能的组合lists；
通过回溯寻找符合要求的字符串，参数为若干个字符arr、字符是否使用过used、遍历到第j个字符、使用了的字母deque）；

五、Java算法源码

public class Test04 {// 可能的组合private static List<List<String>> lists = new ArrayList<>();public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = Integer.valueOf(sc.nextLine());String[] arr = sc.nextLine().split(" ");// 升序排序Arrays.sort(arr);// 使用了的字母Deque<String> deque = new ArrayDeque<>();// 字母是否使用过boolean[] used = new boolean[n];dfs(arr, used, 0, deque); // 递归每一层for (int i = 0; i < lists.size(); i++) {  // 输出结果System.out.println(String.join("", lists.get(i)));}}/*** 通过回溯寻找符合要求的字符串* @param arr 若干个字符* @param used 字符是否使用过* @param j 遍历到第j个字符* @param deque 使用了的字母*/public static void dfs(String[] arr, boolean[] used, int j, Deque<String> deque) {if (j == arr.length) {// 符合要求的字符串集合lists.add(new ArrayList<>(deque));return;}for (int i = 0; i < arr.length; i++) {// 如果使用过，则跳出if (used[i]) {continue;}if (i > 0 && arr[i].equals(arr[i - 1]) && !used[i - 1]) {continue;}deque.addLast(arr[i]);used[i] = true;// 通过回溯寻找符合要求的字符串dfs(arr, used, j + 1, deque);deque.removeLast();used[i] = false;}}
}