[数据结构与算法]字符串的组合问题——返回字符串的所有不重复子序列

题目

你有一套字母卡片tiles，卡片上印有一个大写字母，这套卡片里可能有重复的字母。返回这套卡片可能排列的非空字母序列的数目。注意每张卡片只能用一次。
提示：

1. 1 <= tiles.length <= 7
2. tiles 由大写英文字母组成
   输入描述：共一行，一个字符串
   输出描述：共一行，一个整形数字，表示结果。

示例：
输入：AAB
输出：8
解释：存在8个满足题意的组合：A 、AA、AB、AAB、ABA、B、BA、BAA

题解

import java.util.*;

public class Main{
    static HashSet<String> ans = new HashSet<>();
    static Set<String> result = new HashSet<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        char[] array = s.toCharArray();
        combiantion(array);
        System.out.println(ans.size());
    }

    public static void combiantion(char chs[]) {
        if (chs.length == 0) {
            return;
        }
        HashSet<String> hashSet = new HashSet<String>();
        Stack<Character> stack = new Stack<Character>();
        for (int i = 1; i <= chs.length; i++) {
            combine(chs, 0, i, stack, hashSet);
        }
        for (String s : hashSet) {
            String s1 = s.replace("[", "").replace("]", "").replace(",", "").replace(" ", "");
            List<String> permute = permutation(s1);
            ans.addAll(permute);
        }
    }

    public static void combine(char[] chs, int begin, int number, Stack<Character> stack, HashSet<String> hashSet) {
        String s = stack.toString();
        if (number == 0 && !hashSet.contains(s)) {
            hashSet.add(s);
            return;
        }
        if (begin == chs.length) {
            return;
        }
        stack.push(chs[begin]);
        combine(chs, begin + 1, number - 1, stack, hashSet);
        stack.pop();
        combine(chs, begin + 1, number, stack, hashSet);
    }

    public static ArrayList<String> permutation(String str) {
        if (str == null || str.length() < 1) {
            return new ArrayList();
        }
        boolean[] visited = new boolean[str.length()];
        process(str, "", visited);
        ArrayList<String> ans = new ArrayList<>(result);
        Collections.sort(ans);
        return ans;
    }

    private static void process(String s, String letter, boolean[] visted) {
        if (s.length() == letter.length()) {
            result.add(letter);
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            char temp = s.charAt(i);
            if (visted[i]) {
                continue;
            }
            visted[i] = true;
            process(s, letter + String.valueOf(temp), visted);
            visted[i] = false;
        }
    }
}

代码参考：庄小焱