全排列，利用回溯法

今天学习了一种全排列的新思路，也是回溯法实现的

 /*递归求全排列，思想为回溯法
        对于无重复值的情况
     *如“abc”
        选中a之后，就不能再选a,只能选b和c
        之后递归选中a和b，只能选c
    */
    public static ArrayList<String> PermutationList_wuchongfuzhi(String str){
        ArrayList<String> result = new ArrayList<>();
        char[] chs = str.toCharArray();//原字符串转为数组处理
        char[] temp = new char[chs.length];//用来存排列后的数组
        boolean[] ifuse = new boolean[chs.length];//该数字是否选择
        PermutationList_backtrace_Core(chs, temp, ifuse,0, result);
        return result;
    }
    public static void PermutationList_backtrace_Core(char[] chs, char[] temp, boolean[] ifuse, int count, ArrayList<String> list){
        if(count == temp.length){
            list.add(String.valueOf(temp));
            return;
        }
        for(int i = 0; i<chs.length; i++){
            if(ifuse[i] == false){//选择还未选中的数字
                temp[count] = chs[i];
                ifuse[i] = true;
                PermutationList_backtrace_Core(chs,  temp, ifuse,count+1, list);
                ifuse[i] = false;

            }
        }
    }

如果有重复值，根据上面的思路修改了一下

 //【扩展】如果有重复值，去除重复值
    public static ArrayList<String> PermutationList_chongfuzhi(String str){
        ArrayList<String> result = new ArrayList<>();
        char[] chars = str.toCharArray();
        char[] temp = new char[chars.length];
        boolean[] ifuse = new boolean[chars.length];
        PermutationList_backtrace_chongfuzhi_Core(chars, temp, ifuse,0, result);
        return result;
    }
    public static void PermutationList_backtrace_chongfuzhi_Core(char[] chs, char[] temp, boolean[] ifuse, int count, ArrayList<String> list){
        if(count == temp.length){
            list.add(String.valueOf(temp));
            return;
        }
        int front = 0;//存上一个值，与下一次的比较，如果重复就不再递归
        for(int i = 0; i<chs.length; i++){
            if(ifuse[i] == false){
                temp[count] = chs[i];
                if(front == chs[i]){//如果有重复继续循环下次，不递归
                    continue;
                }
                ifuse[i] = true;
                PermutationList_backtrace_chongfuzhi_Core(chs,  temp, ifuse,count+1, list);
                ifuse[i] = false;
                front = chs[i];//将这次的值赋给front
            }
        }
    }