498，回溯算法解活字印刷

Original 山大王wld 数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

If you lose your purpose, it's like you're broken.

如果你生活漫无目的，那就好像你坏了。

问题描述

你有一套活字字模tiles，其中每个字模上都刻有一个字母tiles[i]。返回你可以印出的非空字母序列的数目。

注意：本题中，每个活字字模只能使用一次。

示例 1：

输入："AAB"
输出：8
解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。

示例 2：

输入："AAABBC"
输出：188

提示：

1 <= tiles.length <= 7
tiles 由大写英文字母组成

回溯算法解决

这题实际上是让求输入的字符可以组成多少种不同的组合。之前也讲过很多种类似这样的题

391，回溯算法求组合问题

448，组合的几种解决方式

451，回溯和位运算解子集

但不同的是前面几道题字符出现的顺序是不会变的，比如第451题，他的子集有123，但不能有321。但这题不一样，输入AAB，他的序列中，A可以在B的前面也可以在B的后面。那么这道题使用回溯算法该怎么解，我们就以示例1为例来画个图看一下

前面介绍的几个组合的回溯算法，因为结果不能有重复的（比如[1，3]和[3，1]被认为是重复的结果），所以每次选择的时候都只能从前往后选。但这题中子集[A，B]和[B，A]被认为是两种不同的结果，所以每次都要从头开始选择，因为每个字符只能被使用一次，所以如果使用之后下次就不能再使用了，这里可以使用一个数组visit来标记有没有被使用。

但这里有个难点就是怎么过滤掉上面图中灰色的部分（也就是重复的部分）。举个例子，比如ABBCD，如果我们选择了第1个B，那么剩余的字符就变成了ABCD，这个时候我们再选择第2个B是可以的。但如果我们没选择第1个B，直接选择第2个B，那么剩余的字符就是ABCD，和上面重复了。所以代码大致是这样的

1if (i - 1 >= 0 && chars[i] == chars[i - 1] && !used[i - 1])
2            continue;

在前面讲450，什么叫回溯算法，一看就会，一写就废的时候，回溯算法的模板也被多次提及

 1private void backtrack("原始参数") {
 2    //终止条件(递归必须要有终止条件)
 3    if ("终止条件") {
 4        //一些逻辑操作（可有可无，视情况而定）
 5        return;
 6    }
 7
 8    for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
 9        //一些逻辑操作（可有可无，视情况而定）
10
11        //做出选择
12
13        //递归
14        backtrack("新的参数");
15        //一些逻辑操作（可有可无，视情况而定）
16
17        //撤销选择
18    }
19}

最后来看下这题的最终代码

 1public int numTilePossibilities(String tiles) {
 2    char[] chars = tiles.toCharArray();
 3    //先排序，目的是让相同的字符挨着，在下面计算的时候好过滤掉重复的
 4    Arrays.sort(chars);
 5    int[] res = new int[1];
 6    backtrack(res, chars, new boolean[tiles.length()], tiles.length(), 0);
 7    return res[0];
 8}
 9
10private void backtrack(int[] res, char[] chars, boolean[] used, int length, int index) {
11    //如果没有可以选择的就返回
12    if (index == length)
13        return;
14    //注意，这里的i每次都是从0开始的，不是从index开始
15    for (int i = 0; i < length; i++) {
16        //一个字符只能选择一次，如果当前字符已经选择了，就不能再选了。
17        if (used[i])
18            continue;
19        //过滤掉重复的结果
20        if (i - 1 >= 0 && chars[i] == chars[i - 1] && !used[i - 1])
21            continue;
22        //选择当前字符，并把它标记为已选择
23        used[i] = true;
24        res[0]++;//选择一个字符，就多了一种结果
25        //下一分支继续递归
26        backtrack(res, chars, used, length, index + 1);
27        //使用完之后再把它给复原。
28        used[i] = false;
29    }
30}

这里还可以换一种写法，先统计每个字符的数量，然后再使用，代码如下。原理都类似，但他不需要去重，因为这里根本不可能出现重复的。

 1public int numTilePossibilities(String tiles) {
 2    char[] chars = tiles.toCharArray();
 3    //统计每个字符的数量
 4    int[] count = new int[26];
 5    for (char c : chars)
 6        count[c - 'A']++;
 7    int[] res = new int[1];
 8    backtrack(res, count);
 9    return res[0];
10}
11
12private void backtrack(int[] res, int[] arr) {
13    //遍历所有的字符
14    for (int i = 0; i < 26; i++) {
15        //如果当前字符使用完了再查找下一个
16        if (arr[i] == 0)
17            continue;
18        //如果没使用完就继续使用，然后把这个字符的数量减1
19        arr[i]--;
20        //使用一个字符，子集数量就会多一个
21        res[0]++;
22        backtrack(res, arr);
23        //当前字符使用完之后，把它的数量还原
24        arr[i]++;
25    }
26}