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

public static String[] generatePermutation(String str) {
        char[] s = str.toCharArray();
        HashSet<String> set = new HashSet<>();
        f1(s, 0, new StringBuilder(), set);

        f1(s,0,new StringBuilder(),set);
        // 转换为列表并排序
        List<String> list = new ArrayList<>(set);
        Collections.sort(list);  // 字典序排序

        return list.toArray(new String[0]);
    }

    // s[i...]：从位置i开始处理
    // path：当前已构建的路径
    // set：收集所有结果并去重
    public static void f1(char[] s, int i, StringBuilder path, HashSet<String> set) {
        if (i == s.length) {
            // 到达末尾，将当前路径加入结果集
            set.add(path.toString());
        } else {
            // 选择1：要当前字符
            path.append(s[i]);
            f1(s, i + 1, path, set);
            path.deleteCharAt(path.length() - 1); // 恢复现场

            // 选择2：不要当前字符
            f1(s, i + 1, path, set);
        }
    }

 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

public static String[] generatePermutation(String str) {
        char[] s = str.toCharArray();
        HashSet<String> set = new HashSet<>();
        f2(s, 0, new char[s.length], 0, set);

        // 转换为列表并排序
        List<String> list = new ArrayList<>(set);
        Collections.sort(list);  // 字典序排序

        return list.toArray(new String[0]);
    }

    // s[i...]：从位置i开始处理
    // path：固定大小的字符数组
    // size：path中已填入的字符个数
    // set：收集结果并去重
    public static void f2(char[] s, int i, char[] path, int size, HashSet<String> set) {
        if (i == s.length) {
            // 只使用path的前size个字符
            set.add(String.valueOf(path, 0, size));
        } else {
            // 选择1：要当前字符
            path[size] = s[i];
            f2(s, i + 1, path, size + 1, set);

            // 选择2：不要当前字符
            f2(s, i + 1, path, size, set);
        }
    }