全排列

全排列，用递归回溯来完成。
我这里的思路是把所有的字符分成两部分，一部分是已经排列的，另一部分是还未排列的。
每一次for循环都会遍历还未排列的字符，把它加入到已经排列的那一部分，然后再进入下一层递归，递归返回要恢复原样。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Arrays;

public class Solution {
    ArrayList<String> ans = new ArrayList<>();

    void dfs(StringBuilder sb, LinkedList<Character> list){
        int l = list.size();
        if(l==0){
            String result = sb.toString();
            if(!ans.contains(result)){
                ans.add(result);
            }
            return;
        }
        for(int i=0;i<l;i++){
            Character c = list.get(i);
            sb.append(c);
            list.remove(i);
            dfs(sb, list);
            list.add(i, c);
            sb.deleteCharAt(sb.length()-1);
        }
    }

    public ArrayList<String> Permutation(String str) {
        int l = str.length();
        if(l==0){
            return ans;
        }
        char[] cArr = new char[l];
        for(int i=0;i<l;i++){
            cArr[i] = str.charAt(i);
        }
        // 确保有序，得先排序
        Arrays.sort(cArr);
        // 链表适合中间删除插入元素。
        LinkedList<Character> list = new LinkedList<>();
        for(int i=0;i<cArr.length;i++){
            list.add(cArr[i]);
        }
        // StringBuilder 适合字符串的频繁更改
        StringBuilder sb = new StringBuilder();
        dfs(sb, list);
        return ans;
    }
}