題目：輸入一個(gè)字符串（可能有重復(fù)字符），求它字符的所有組合。

例：
輸入abc，結(jié)果為[bc, a, ab, b, ac, c, abc]
輸入abac，結(jié)果為[aa, a, bc, ab, ac, b, aac, c, abc, aab, aabc]

解法一：每個(gè)字符都可選，可不選，即每個(gè)字符有兩種可能，以abc舉例，抽象成一棵二叉樹，如下(帶角標(biāo)的代表不選，如 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 結(jié)果集
     * sb 當(dāng)前組合起來(lái)的字符串
     * index 當(dāng)前正在操作的字符的下標(biāo)
     * str 字符數(shù)組
     **/
    private void dfs(List<String> result, String sb, int index, char[] str) {
        // 當(dāng)最后一個(gè)字符已經(jīng)操作完后，將組合后的字符串放入結(jié)果集
        if (index >= str.length) {
            if (sb.length() > 0) {      // 去除所有字符都不選的結(jié)果，即空字符串""
                // 將結(jié)果重新排序，方便后面去重
                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);
    }

解法二：利用二進(jìn)制，每個(gè)字符代表二進(jìn)制中的一位，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);
    }

    // 根據(jù)num確定哪些字符被選了，例如以abc舉例，3=011，選了b和c
    private void getString(int num, List<String> result, char[] str) {
        // index表示當(dāng)前在處理的字符下標(biāo)，從最后一位字符開始
        int index = str.length - 1;    
        // 保存選中的字符下標(biāo)，方便后面組合字符串
        List<Integer> indexes = new ArrayList<>();  
        // 將num模2，如果結(jié)果為1，說(shuō)明index所在的字符被選中，將index放入indexes。
        // 然后將num右移一位（就是除2啦），同時(shí)將index-1指向前一個(gè)字符。
        // 重復(fù)此過(guò)程，直到num==0
        while (num != 0) {
            if (num % 2 == 1) {
                indexes.add(index);
            }
            num /= 2;
            --index;
        }
        StringBuilder sb = new StringBuilder();
        // 將選中的字符組合成字符串，并對(duì)字符重新排序，方便去重，然后放入結(jié)果集中
        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));
    }