1、前言

2、思路

这道题就是全排列，全排列分两种，一种是无重复数字，那么其实不用考虑去重问题，直接把所有结果都放进去。

但是还有重复字符的全排列，结果需要去重复，去重的重点是先排序（方便减枝），然后有重复的第二个直接跳过即可：i > 0 && array[i] == array[i - 1] && used[i - 1

3、代码

class Solution {

    private List<String> res = new ArrayList<>();

    public String[] permutation(String s) {
        if(s == null || s.length() == 0){
            return new String[]{};
        }
        char[] array = s.toCharArray();
        Arrays.sort(array);
        boolean[] used = new boolean[s.length()];
        dfs(array, new StringBuilder(), used);

        return res.toArray(new String[]{});
    }

    private void dfs(char[] array, StringBuilder builder, boolean[] used){
        if(builder.length() == array.length){
            res.add(builder.toString());
            return;
        }

        for(int i = 0; i < array.length; i++){
            if(used[i]){
                continue;
            }
            if(i > 0 && array[i] == array[i - 1] && used[i - 1]){
                continue;
            }
            used[i] = true;
            builder.append(array[i]);
            dfs(array, builder, used);
            used[i] = false;
            builder.deleteCharAt(builder.length() - 1);
        }
    }
}