1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

ArrayList<String> ans = new ArrayList<>();
    public ArrayList<String> Permutation(String str) {

        StringBuilder sb = new StringBuilder();
        boolean[] used = new boolean[str.length()];
        char[] chs = str.toCharArray();
        Arrays.sort(chs);
        str = new String(chs);
        backtrack(str, sb, used);
        return ans;
    }

    private void backtrack(String str, StringBuilder sb, boolean[] used) {
        if (sb.length() == str.length()) {
            ans.add(new String(sb));
            return;
        }

        for (int i = 0; i < str.length(); i++) {
            if (used[i]) {
                continue;
            }
            if (i > 0 && str.charAt(i) == str.charAt(i - 1) && !used[i - 1]) {
                continue;
            }
            sb.append(str.charAt(i));
            used[i] = true;
            backtrack(str, sb, used);
            sb.deleteCharAt(sb.length() - 1);
            used[i] = false;

        }
    }