字符串的排列

回溯法
调用回溯函数，先判断是否满足结束条件，若满足将其加入序列，return；若不满足使用循环进行回溯。典型的题目有全排列等。
必要的几个参数：
1、标志位数组used[]
2、存储中间结果的容器，如一个String、一个ArrayList等
3、题目中给的已知参数和要返回的结果
代码如下：

import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList<>();
        if(str.length()==0 || str==null){
            return res;
        }
        int used[] = new int[str.length()];
        String temp="";
        backTrack(str,used,temp,res);
        //按字典序
        Collections.sort(res);
        return res;
    }

    public void backTrack(String str,int used[],String temp,ArrayList<String> res){
        if(temp.length()==str.length()){
            res.add(temp);
            return;
        }else{
            for(int i=0;i<str.length();i++){
                if(used[i]==1) continue;
                if(i!=0 && str.charAt(i)==str.charAt(i-1)&& used[i-1]==1) continue;

                temp = temp+str.charAt(i);
                used[i]=1;
                backTrack(str,used,temp,res);

                used[i]=0;
                temp = temp.substring(0,temp.length()-1);
            }
        }

    }
}