字符串的排列（全排列）——Java回溯法

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

Solution：

20180619204217111.png

从这张图中，我们可以看出来，找全排列类似于深度优先遍历，深度优先最关键的就是要记住上一个状态，而所谓回溯就是要回到上一没有操作过的状态，再去考虑别的情况。

···
import java.util.*;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> ans=new ArrayList<>();//所有排列的可能都在这里
if(str!=null||str.length()>0){
help(0,str.toCharArray(),ans);
Collections.sort(ans);
}
return ans;
}
public static void help(int i,char[] cha,ArrayList<String> ans){
if(i==cha.length-1){
String val = String.valueOf(cha);
if(!ans.contains(val)){
ans.add(val);
}
}else{
for(int j=i;j<cha.length;j++){
swap(i,j,cha);//依次选一个数固定住
help(i+1,cha,ans);//让后面的进行全排列
swap(i,j,cha);//恢复原来的模样，回溯关键
}
}
}
public static void swap(int i,int j,char[] cha){
char temp=cha[i];
cha[i]=cha[j];
cha[j]=temp;
}
}
···