题解 | #递归，全排列，回溯#

import java.util.*;
public class Solution {
    //交换法
    public ArrayList<String> Permutation(String str) {
       HashSet<String> set = new HashSet<>() ;
       helper(str.toCharArray() , 0 , set) ;
       ArrayList<String> res = new ArrayList<>(set) ;
        return res ;
    }
    
    //求arr[loc,,,,]的全排列
    public void helper(char[] arr , int loc , HashSet<String> res) {
        if(loc == arr.length-1) {//若loc是最后一个位置，则不用交换，证明一次排列已经完成
            res.add(new String(arr)) ;    
        }
        for(int i = loc ; i < arr.length ; i ++) {
            swap(arr,i,loc) ;//让loc之后的每一个位置与loc交换
            helper(arr,loc+1,res) ;//交换之后求loc+1之后的全排列
            swap(arr,i,loc) ;//还原，准备下一次交换
        }
    }
    public void swap(char[] arr , int index1 , int index2) {
        char t = arr[index1] ;
        arr[index1] = arr[index2] ;
        arr[index2] = t ;
    }
}