题解 | #字符串的排列#

import java.util.*;


public class Solution {
    Set<String> ret = new HashSet<>(); 
    //ArrayList<String> ret ;

     StringBuilder path ; //记录走过的字符
     boolean[] check; // 下标对应字符是否被选中过
    public  ArrayList<String> Permutation (String str) {
         //ret = new ArrayList<String>();
         // if(str.length()==1){
        //     ret.add(str);
        //     return ret;
        // }
        check = new boolean[10];
        path = new StringBuilder();
        dfs(str);
         ArrayList<String> res = new ArrayList<>(ret);
       
        return res;
    }

    //深度优先遍历字符串将结果加入ret
    public  void dfs(String str){

        //结束情况
        if(path.length()==str.length()){
            ret.add(new String(path));
            return;
        }
        //遍历字符串，挨个选择字符得出结果
        for(int i=0;i<str.length();i++){
            //当没有选中过该字符时加入路径
            if(check[i]==false){
                path =path.append(str.charAt(i));
                check[i] = true;
                //进行下一层dfs
                dfs(str);
                //dfs结束回溯
                check[i] = false;
                path.deleteCharAt(path.length()-1);
            }
        }
    }
}