描述
输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。
数据范围：n<10
要求：空间复杂度 O(n!)，时间复杂度 O(n!)
输入描述：
输入一个字符串,长度不超过10,字符只包括大小写字母。
示例1
输入："ab"
返回值：["ab","ba"]
说明：返回["ba","ab"]也是正确的
示例2
输入："aab"
返回值：["aab","aba","baa"]
示例3
输入："abc"
返回值：["abc","acb","bac","bca","cab","cba"]
示例4
输入：""
返回值：[""]
思路
这道题就是一个组合，但是要排除重复项。如果直接使用循环，好像并不好下手。
如果我们使用递归的思想，把字符串abc看作a和[bc]的组合。我们不用关心[bc]组合到底是什么样子，我们最终得到以a开头的组合就是a+[bc]。以b开头的组合b+[ac],以c开头的组合c+[ab]。
在计算以a开头的组合中，我们还需要判断如果[bc]中有以a开头的字符。比如aab这种用例的情况，a+[ab]，后面进行遍历的时候，我们就不再统计a，直接统计b+[aa]。所以最终结果就是aab aba,baa。
大致思路其实已经出来了，伪代码如下：
permutation(abc) {
list = [];
set = [];
for(a,b,c):
if(!set.contains(a)){
sublist = permutation(bc)
for(String str: sublist):
list.add(a+str)
set.add(a);
}
return list;
}
在上面aab的例子中，我们开始遍历a的时候，我们需要知道[ab]有多少种组合，这样，结果就是a + list([ab]) ，继续拆分ab，这时候就是a+list([b])。当只有一个字母的时候，组合就是一种情况，递归终止。当进行下一次遍历的时候，发现如果是a，那么不用遍历，因为a已经计算过。最后遍历到b，这时候就是b+list([aa])，继续拆分aa，同样是一种情况，最终遍历结束，返回所有的情况。
同理，abc的时候，我们遍历a，我们需要知道剩下的[bc]的组合情况，继续拆分b+[c]。拆到只剩一个字母的时候，递归结束。接着遍历b、c。为了求出剩下的字符有多少种组合，我们继续拆分，也就是递归，直到剩下一个字母，这时候就是一种情况，递归结束。
代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
System.out.println(Permutation(scanner.next()));
}
scanner.close();
}
public static ArrayList<String> Permutation(String str) {
ArrayList<String> list = new ArrayList<>();
if (str.length() == 1) {
list.add(str);
} else {
Set<String> set = new HashSet<>();
for (int i = 0; i < str.length(); i++) {
String left = str.substring(i, i + 1);
if (!set.contains(left)) {
String substr = str.substring(0, i) + str.substring(i + 1);
List<String> subList = Permutation(substr);
for (int j = 0; j < subList.size(); j++) {
list.add(left + subList.get(j));
}
set.add(left);
}
}
}
return list;
}
}
运行测试用例：
这道题采用了递归的思想，把字符串拆分为首字母和剩下的子串，这种组合就是首字母和子串列表的组合。 为了求得子串有多少种组合，继续拆分，直到拆分到剩下一个字符串，这时候就是一种情况，拆分结束。当然，字符串有可能会有字母重复，我们在遍历的时候，记录是否已经遍历过当前首字母。
还有一种比较孬的办法，这里不用考虑重复，把所有可能的情况都添加进来，最后把结果放到Set集合中，让它自己去重，虽然也能得到结果，但是时间复杂度不一定能满足算法要求。
而本例的方法是通过了算法测试要求的：
这种使用递归的办法，我们不需要知道每一种组合到底有多少种，我们只需要根据我们的思路去把字符串拆分成更小的单元，到了一个字母组成的字符串的时候，我们就很明确地知道这种组合情况，递归结束。
最后附上牛客网该题的地址：https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7
