全排列（有重复序列）

题目：
输入一个字符串，打印出该字符串中字符的所有排列（存在重复的字符），
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例：

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

输入：s = "abb"
输出：["abb","bab","bba"]

该题类似于【全排列（无重复序列）】，但该题需要考虑有重复字符的情况：
当有重复字符时，我们需要过滤掉（俗称：）。

来看看 不重复 与 重复 两张图：

• 不重复：算法与全排列（无重复序列一样）

  
  111.png

• 有重复：需要在交换之前先判断是否已选择过，已选择就剪枝，不用再继续！

  
  222.png

具体的算法：

public class Main {
    private static List<String> list = new ArrayList<>();

    public static void main(String[] args) {
        String[] a = permutation("abb");
        System.out.println(Arrays.toString(a));
    }

    public static String[] permutation(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }

        dfs(s.toCharArray(), 0);
        return list.toArray(new String[list.size()]);
    }

    private static void dfs(char[] ch, int pos) {
        if (pos == ch.length) {
            list.add(String.valueOf(ch));
            return;
        }

        // 利用 HashSet 来判断是否已添加过
        Set<Character> sets = new HashSet<>();
        for (int i = pos; i < ch.length; i++) {
            if (sets.contains(ch[i])) continue; // 已选择过，剪枝
            sets.add(ch[i]); // 未选择过，加入 HashSet
            
            // 后面与无重复序列一样：交换、下一步选择、撤回
            swap(ch, pos, i);
            dfs(ch, pos + 1);
            swap(ch, pos, i);
        }
    }

    private static void swap(char[] ch, int i, int j) {
        char temp = ch[i];
        ch[i] = ch[j];
        ch[j] = temp;
    }
}