40、字符串的组合

题目：输入一个字符串（可能有重复字符），求它字符的所有组合。

例：
输入abc，结果为[bc, a, ab, b, ac, c, abc]
输入abac，结果为[aa, a, bc, ab, ac, b, aac, c, abc, aab, aabc]

解法一：每个字符都可选，可不选，即每个字符有两种可能，以abc举例，抽象成一棵二叉树，如下(带角标的代表不选，如 a'代表不选a )：

image.png(a'代表不选a)

  private List<String> combination(String str) {
        List<String> result = new ArrayList<>();
        if (str == null || str.length()==0) return result;
        dfs(result, "", 0, str.toCharArray());
        HashSet<String> set = new HashSet<>(result);    // 去重
        return new ArrayList<>(set);
    }

    /**
     * result 结果集
     * sb 当前组合起来的字符串
     * index 当前正在操作的字符的下标
     * str 字符数组
     **/
    private void dfs(List<String> result, String sb, int index, char[] str) {
        // 当最后一个字符已经操作完后，将组合后的字符串放入结果集
        if (index >= str.length) {
            if (sb.length() > 0) {      // 去除所有字符都不选的结果，即空字符串""
                // 将结果重新排序，方便后面去重
                char[] chars = sb.toCharArray();
                Arrays.sort(chars);
                result.add(new String(chars));
            }
            return;
        }
        // 不选index所在的字符
        dfs(result, sb, index + 1, str);
        // 选index所在的字符
        dfs(result, sb + str[index], index + 1, str);
    }

解法二：利用二进制，每个字符代表二进制中的一位，0代表不选，1代表选。例如：abc，用111表示，即用7=2^3-1 表示；a=100，b=010，c=001，ab=110，以此类推。共有7=2^3-1种可能。

private List<String> combination(String str) {
        List<String> result = new ArrayList<>();
        if (str == null || str.length()==0) return result;
        int max = (int) (Math.pow(2, str.length()) - 1);
        char[] chars = str.toCharArray();
        // i从1开始，去掉空字符串的可能
        for (int i = 1; i <= max; ++i) {
            getString(i, result, chars);
        }
        HashSet<String> strings = new HashSet<>(result);
        return new ArrayList<>(strings);
    }

    // 根据num确定哪些字符被选了，例如以abc举例，3=011，选了b和c
    private void getString(int num, List<String> result, char[] str) {
        // index表示当前在处理的字符下标，从最后一位字符开始
        int index = str.length - 1;    
        // 保存选中的字符下标，方便后面组合字符串
        List<Integer> indexes = new ArrayList<>();  
        // 将num模2，如果结果为1，说明index所在的字符被选中，将index放入indexes。
        // 然后将num右移一位（就是除2啦），同时将index-1指向前一个字符。
        // 重复此过程，直到num==0
        while (num != 0) {
            if (num % 2 == 1) {
                indexes.add(index);
            }
            num /= 2;
            --index;
        }
        StringBuilder sb = new StringBuilder();
        // 将选中的字符组合成字符串，并对字符重新排序，方便去重，然后放入结果集中
        for (int i = indexes.size() - 1; i >= 0; --i) {
            sb.append(str[indexes.get(i)]);
        }
        char[] chars = sb.toString().toCharArray();
        Arrays.sort(chars);
        result.add(new String(chars));
    }