剑指 Offer 38. 字符串的排列

先固定第一位有n种，然后第二位有(n - 1)种，依次类推。
当字符串中存在重复字符时，排列中也会出现重复的方案。为排除重复方案，需在固定某位字符时，保证 “每种字符只在此位固定一次” ，即遇到重复字符时不交换，直接跳过。从 DFS 角度看，此操作称为 “剪枝” 。

class Solution {
    
    List<String> res = new ArrayList<>();
    char[] arr;
    public String[] permutation(String s) {
    
        arr = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    //回溯函数
    void dfs(int x){
    
        if(x == arr.length-1){
    
            res.add(String.valueOf(arr));
            return;
        }
        Set<Character>set = new HashSet<>();
        for(int i = x; i<arr.length; i++){
    
            if(set.contains(arr[i])){
    continue;}//重复的剪枝
            set.add(arr[i]);
            swap(i,x);
            dfs(x+1);
            swap(i,x);
        }
    }
    //交换函数
    void swap(int a,int b){
    
        char ch = arr[a];
        arr[a] = arr[b];
        arr[b] = ch;
    }
}

中间交换递归方面不太明确。