lc1079 Letter Tile Possibilities

利用递归解决

观察题目给出的例子

AAB 按照长度分

A, B

AA, AB, BA

AAB, ABA, BAA

不难发现，长度为n的解可由长度为n-1的解推出

利用递归，每次长度为n的解可以递归了化简至长度为1

而且为了避免记录组合结果以用来每次比较组合成的结果是否曾经出现过，例如AA和AB都可以生成AAB。

我们需要写递归时将每次的增量，即新增字母，固定为26个字母，而不是剩下字母的次数。

举例来说，当调用到最底层长度为1，只剩一个B时，他的上一层是长度为2，但是还剩两个A，显然，只能用一次A作为增量，而不能按照字母剩下的次数，计算两次+A。

 

 1 class Solution {
 2     public int numTilePossibilities(String tiles) {
 3         if(tiles.length() == 0)
 4             return 0;
 5         int[] count = new int[26];
 6         
 7         for(char c : tiles.toCharArray())
 8                count[c-'A']++;
 9         return dfs(count);
10     }
11     
12     private int dfs(int[] array){
13         int sum = 0;
14         
15         for(int i=0; i<26; i++){
16             if(array[i] == 0)
17                 continue;
18             
19             sum++;
20             array[i]--;
21             sum += dfs(array);
22             array[i]++;
23         }
24         return sum;
25     }
26 }