题解 | #字符串的排列#

递归函数功能：
收入 当前得到的字符串+剩余的可取字符集
操作 保存这两个参数，以便回溯
遍历可取字符集
--1.将该字符取出加入到当前字符串，把新的字符串和可取集传下去(子递归)
--2.从上一个递归返回后，把此时的字符串和可取集回溯到初值

主要思路：循环递归、复制初值以回溯、利用set消重(最开始用set接收，后面遍历取出来的时候虽然结果全都有，但是hashset的顺序不一样，所以这里仅用set作判断，可放入则加入结果列表，不可放入则是重复，丢掉)

import java.util.*;
//用模拟取出换实现   递归 回溯 消重  *千万要搞清楚复制和引用的区别，回溯的断点这里用引用又卡了两小时，吐血
public class Solution {
    static HashSet Fin1=new HashSet();
    static ArrayList Fin=new ArrayList();
    public ArrayList Permutation(String str) {
        //把字符串转化为ArryList   able
        char[] x = str.toCharArray();
        ArrayList able = new ArrayList();
        for (int i = 0; i <=x.length-1 ; i++) {
            able.add(x[i]);
        }
        //开一个空的起始StringBuffer
        StringBuffer start=new StringBuffer();
        //前者表示当前字符串，后者表示剩余可用字符集
        fun(start,able);
        return Fin;
    }
    public void fun(StringBuffer result,ArrayList able){
        //接收当前字符串  开res副本接收result、able1接收able，且以便回溯
        StringBuffer res=new StringBuffer(result);
        ArrayList able1=new ArrayList(able);
        //
        if(able.size()==0){
            //尝试把结果字符串放入set结果集
            if(Fin1.add(res.toString())){
                Fin.add(res.toString());
            };
        }
        if(able.size()!=0) {
            //从可用字符集中取一个加到当前字符串
            for (int i = 0; i <=able.size()-1 ; i++){
                res.append(able.get(i));
                able1.remove(i);
                fun(res, able1);
                //这里要回溯，恢复到刚传入的result和able值
                able1=new ArrayList(able);
                res=new StringBuffer(result);
            }
        }
    }
}