#yyds干货盘点# LeetCode程序员面试金典：有重复字符串的排列组合

题目：

有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

示例1:

输入：S = "qqe"

输出：["eqq","qeq","qqe"]

示例2:

输入：S = "ab"

输出：["ab", "ba"]

代码实现：

class Solution {
    List<String> permutations = new ArrayList<String>();
    StringBuffer temp = new StringBuffer();
    char[] arr;
    int n;
    boolean[] visited;

    public String[] permutation(String s) {
        arr = s.toCharArray();
        Arrays.sort(arr);
        this.n = s.length();
        this.visited = new boolean[n];
        backtrack(0);
        return permutations.toArray(new String[permutations.size()]);
    }

    public void backtrack(int index) {
        if (index == n) {
            permutations.add(temp.toString());
        } else {
            for (int i = 0; i < n; i++) {
                if (visited[i] || (i > 0 && arr[i] == arr[i - 1] && !visited[i - 1])) {
                    continue;
                }
                temp.append(arr[i]);
                visited[i] = true;
                backtrack(index + 1);
                temp.deleteCharAt(index);
                visited[i] = false;
            }
        }
    }
}