Question

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

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

思路：回溯。

固定A不动，然后交换B与C，从而得到"ABC" 和 "ACB" 同理，对于"BAC"、"BCA" 、"CAB"和"CBA"是同样道理。 当两个字符相同时，不应该交换。

• 递归函数的功能：dfs(int pos, string s), 表示固定字符串s的pos下标的字符s[pos]
• 递归终止条件：当pos+1 == s.length()的时候，终止，表示对最后一个字符进行固定，也就说明，完成了一次全排列
• 下一次递归：dfs(pos+1, s), 很显然，下一次递归就是对字符串的下一个下标进行固定

回溯：每次递归完成后，须重新交换回来。

import java.util.ArrayList;
import java.util.Collections;
public class Solution 
{
  public ArrayList<String> Permutation(String str)
  {
    ArrayList<String> res=new ArrayList<String>();
    if(str.length()==0||str==null)return res;
    int n= str.length();
    helper(res,0,str.toCharArray());
    Collections.sort(res);
    return res;
     
  }
  public void helper( ArrayList<String> res,int index,char []s)
  {
    if(index==s.length-1)res.add(new String(s));
    for(int i=index;i<s.length;i++)
    {
      if(i==index||s[index]!=s[i])
      {
        swap(s,index,i);
        helper(res,index+1,s);
        swap(s,index,i);
      }
    }
     
  }
   
  public void swap(char[]t,int i,int j)
   {
    char c=t[i];
    t[i]=t[j];
    t[j]=c;
  }
}