题目

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

思考

1、注意要去重
2、排列组合=》回溯
3、使用一个数组来完成去重

代码和注释

/**
    全排列
    =》回溯
 */
class Solution {
    // 结果集
    List<String> res = new ArrayList<>();

    String[] result = null;

    public String[] permutation(String s) {
        String str="";
        // 用于记录这个值是不是这个值是不是使用过了
        int[] used = new int[s.length()];
        // 排序
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        s = new String(chars);

        backtacking(s, str, used);
        return result;
    }


    public void backtacking(String s, String str, int[] used){
        if(str.length() == s.length()){
            // 收集结果
            res.add(str);
            return;
        }

        for(int i = 0; i < s.length(); i++){
            // 每个节点用过的就不使用了,仅试用于没有重复的值
            // if(str.contains(s.charAt(i)+"")){
            //     continue;
            // }
            if(i>0 && s.charAt(i)==s.charAt(i - 1) && used[i - 1] == 1 ){
                continue;
            }
            if(used[i] == 0){
                used[i] = 1;
                str = str + s.charAt(i);
                backtacking(s,str,used);
                str = str.substring(0, str.length()-1); 
                used[i] = 0;
            }
            
        }
        // 集合转数组
        result = res.toArray(new String[0]);

        // 超时转
        // result = new String[res.size()];

        // for(int i = 0; i< res.size(); i++){
        //     result[i] = res.get(i);
        // }
    }
}