作者：whisper

链接：https://www.proprogrammar.com/article/913

声明：请尊重原作者的劳动，如需转载请注明出处

剑指 Offer 38. 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

限制：

1 <= s 的长度 <= 8

难度：中等；标签：回溯算法；编程语言：JAVA

 其它方法

class Solution {
    // 题解中的解法：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/
    List<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation2(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    void dfs(int x) {
        if(x == c.length - 1) {
            res.add(String.valueOf(c)); // 添加排列方案
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < c.length; i++) {
            if(set.contains(c[i])) continue; // 重复，因此剪枝
            set.add(c[i]);
            swap(i, x); // 交换，将 c[i] 固定在第 x 位 
            dfs(x + 1); // 开启固定第 x + 1 位字符
            swap(i, x); // 恢复交换
        }
    }
    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
}

做过类似的，忘了，题解中的方法，思路很清晰，把每个不同的数分别放在第一位，第二位，第。。。。，如果没有重复的数，第一位有n种情况，第二位有n-1种情况，。。。。，因为可能有重复，所以用set去重，swap的意思是第i位原来的数到后面，构成其它的情况，具体可以看题解方法

亲爱的读者：有时间可以点赞评论一下