【华为校招】【校招】【Java】考古问题

■ 题目描述
考古问题，假设以前的石碑被打碎成了很多块，每块上面都有一个或若干个字符，请你写个程序来把之前石碑上文字可能的组合全部写出来，按升序进行排列。
示例1 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
3
a b c
输出
abc
acb
bac
bca
cab
cba
示例2 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
3
a b a
输出
aab
aba
baa

public class GetOldest {

    static List<String> res = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int len = scanner.nextInt();
            scanner.nextLine();
            String[] strings = scanner.nextLine().split(" ");
            boolean[] used = new boolean[len];
            backtracking(strings, len, used);
            for (String temp :
                    res) {
                System.out.println(temp);
            }
        }
    }

    // 求排列
    private static void backtracking(String[] strings, int len, boolean[] used) {
        if (sb.length() >= len) {
            // 加入结果集
            res.add(sb.toString());
            return;
        }
        // 回溯
        for (int i = 0; i < len; i++) {
            if (used[i]) {
                // 去重
                continue;
            }
            sb.append(strings[i]);
            used[i] = true;
            backtracking(strings, len, used);
            used[i] = false;
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41