27.字符串的排列 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 1.递归全排列法： 先从左往右固定一个字符，让后面所有字符依次与其交换位置，然后递归执行，递归返回后继续对刚交换的字符再交换回来，以保持输入字符串不变。以这种方式遍历所有字符。 还有就是注意审题，题目中要求打印要按照字典序进行，针对这个要求，我们可以对得到的全排列进行排序再返回。
import java.util.ArrayList; import java.util.List; import java.util.Collections; public class Solution { public ArrayList<String> Permutation(String str) { List<String> res = new ArrayList<>(); if (str.length() > 9 || str.length()<1) { return (ArrayList)res; } //递归的初始值为（ch数组，空的list，初始下标0） fullPerm(str.toCharArray(),0,res);//调用字符串排列函数 //按字典序打印出该字符串中字符的所有排列 Collections.sort(res);//排序输出.测试才能通过 return (ArrayList)res; } private void fullPerm(char[] ch,int start,List<String> res){ //递归结束的条件就是，第一位和最后一位交换完成 //考虑添加这一组字符串进入结果集中 if(start==ch.length-1){ String val=String.valueOf(ch); //判断一下该集合中是否有重复字符串 if(!res.contains(val)){ res.add(val); return; } } else{ // 第一次循环i与start相等，相当于第一个位置自身交换，关键在于之后的循环， // 之后i !=start，则会交换两个不同位置上的字符，直到start==ch.length-1，进行输出； for(int i=start;i<ch.length;i++){ //保证当输入多个重复字符时，不会重复计算 if(i!=start&&ch[i]==ch[start]){ //如果第一位和非第一位重复了，就不交换了. countinue; } swap(ch,start,i);//每一次，交换首位置和第i个位置的元素 fullPerm(ch,start+1,res);// //递归，第一位固定了，将除了第一位，后面的字符串全排序。 swap(ch,start,i);//交换完成还要换回来，保证第一位不变 } } } } public void swap(char[] ch, int i, int j) { char temp = ch[i]; ch[i] = ch[j]; ch[j] = temp; } }第二个swap用以使得字符数组的顺序回到进入递归前的状态，这样才不会影响外部的遍历顺序。因为在第一次交换后进入递归运算的时候，字符数组的顺序改变了，例如“abc”， start= 0时对应‘a’，j = 1时对应 ‘b’，进行一次交换，此时的字符数组的顺序为 “bac”，从递归返回时，顺序依然是“bac”，则进行第二次交换使得 “bac” -> “abc”，这样在后续才可以进行’a’与’c’的交换，不会落下某一种情况
2.回溯法 也就是利用树去尝试不同的可能性，不断地去字符串数组里面拿一个字符出来拼接字符串，当字符串数组被拿空时，就把结果添加进结果数组里，然后回溯上一层。（通过往数组加回去字符以及拼接的字符串减少一个来回溯。）
