最优解法

递归解法

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Collections;

public class Solution {
    public ArrayList<String> Permutation(String str){
        if(str.length()==0)
            return new ArrayList<>();
        HashSet<String> res = new HashSet<>();
        Permutations(str.toCharArray(), 0, str.length(), new StringBuffer(), res);
        ArrayList<String> temp = new ArrayList<>(res);
        Collections.sort(temp);
        return temp;
    }

    private void Permutations(char[] chars, int start, int end, StringBuffer sb, HashSet<String> lists){
        if (start == end){
            lists.add(new String(sb));
            return;
        }
        for (int i = 0; i <= sb.length(); i++){
            sb.insert(i, chars[start]);
            Permutations(chars, start + 1, end, sb, lists);
            // 复用对象，减少因新对象的创建所带来的性能消耗
            sb.deleteCharAt(i);
        }
    }
}