一、题目

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

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

二、输入

1
2
第一行输入N，N表示石碑碎片的个数
第二行依次输入石碑碎片上的文字内容S共有N组

三、输出

1
输出石碑文字的组合(按照升序排列)，行尾无多余空格

四、示例

示例一

1
2
3
4
5
6
7
8
9
10
11
输入：
3
a b c

输出：
abc
acb
bac
bca
cab
cba

示例二

1
2
3
4
5
6
7
8
输入：
3
a b a

输出
aab
aba
baa

示例三

1
2
3
4
5
6
7
8
9
10
11
输入：
3
3
a b ab

输出
aabb
abab
abba
baab
baba

五、题解

  1. 理解题目后，就是一个存在重复元素的全排列问题
  2. 和标准排列问题有一点不同的是元素组合后可能跟存在的元素相同如“示例三”，因此需要对最后的结果 Set 去重
  3. 排列中的去重指的是不同位置的元素相同

5.1 Java 实现

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package org.stone.study.algo.ex202411;

import java.util.*;

public class ArchaeologistProblem {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        scanner.nextLine(); // int m 所在行的换行符
        String[] fragments = scanner.nextLine().split(" ");
        // 用set去重，保证结果有序
        LinkedHashSet<String> result = new LinkedHashSet<>();
        Deque<String> oneSolution = new ArrayDeque<>();
        // 标记是否访问过，避免重复访问。比交换元素的算法容易理解一些
        boolean visited[] = new boolean[fragments.length];
        Arrays.fill(visited, false);
        // 先排序，相同的字符串在一起
        Arrays.sort(fragments);
        backtrack(fragments, visited, result, oneSolution);

        result.forEach(System.out::println);
    }

    /**
     * 有重复的全排列，套用回溯模板
     * @param fragments
     * @param visited
     * @param result
     * @param oneSolution
     */
    private static void backtrack(String[] fragments, boolean[] visited, Set<String> result,
                                  Deque<String> oneSolution) {
        if(oneSolution.size() == fragments.length) {
            result.add(String.join("", oneSolution));
            return;
        }

        for(int i = 0; i < fragments.length; i++) {
            if(visited[i]) {
                continue;
            }
            // 去重
            if(i > 0 && fragments[i].equals(fragments[i-1]) && !visited[i-1]) {
                continue;
            }

            visited[i] = true;
            // 选择 Deque 的原因是方便这里处理
            oneSolution.addLast(fragments[i]);
            backtrack(fragments, visited, result, oneSolution);
            visited[i] = false;
            oneSolution.removeLast();
        }
    }
}

5.2 Python实现

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
# 回溯算法
def backtrack(fragments, result, path, used):
    if len(path) == len(fragments):
        result.add("".join(path))
        return

    for i in range(len(fragments)):
        if used[i]:
            continue

        # 剪枝：去重相同的片段
        if i > 0 and fragments[i] == fragments[i - 1] and not used[i - 1]:
            continue 

        used[i] = True
        path.append(fragments[i])
        backtrack(fragments, result, path, used)
        path.pop()
        used[i] = False

def main():
    n = int(input())
    fragments = input().split()
    
    result = set()
    path = []
    used = [False] * n
    fragments.sort()
    backtrack(fragments, result, path, used)

    # set 是无序的，需要排序后输出
    for s in sorted(result):
        print(s)



if __name__ == "__main__":
    main()