本系列導(dǎo)航：劍指offer（第二版）java實(shí)現(xiàn)導(dǎo)航帖

面試題：字符串的組合

題目要求：
輸入一個(gè)字符串，打印出該字符串中字符的所有組合。如輸入abc，則打印a，b，c，ab，ac，bc，abc。

解題思路：
這道題目是在38題.字符串的排列的擴(kuò)展部分出現(xiàn)的。排列的關(guān)鍵在于次序，而組合的關(guān)鍵在于狀態(tài)，即該字符是否被選中進(jìn)入組合中。
對(duì)于無(wú)重復(fù)字符的情況，以a,b,c為例，每一個(gè)字符都有兩種狀態(tài)：被選中、不被選中；2*2*2=8，再排除為空的情況，一共有7種組合：

a(被選中)b(被選中)c(被選中)            =>    abc
a(被選中)b(被選中)c(不被選中)          =>    ab
a(被選中)b(不被選中)c(被選中)          =>    ac
a(被選中)b(不被選中)c(不被選中)        =>    a
a(不被選中)b(被選中)c(被選中)          =>    bc
a(不被選中)b(被選中)c(不被選中)        =>    b
a(不被選中)b(不被選中)c(被選中)        =>    c
a(不被選中)b(不被選中)c(不被選中)      =>    空(不作為一種組合情況)

對(duì)于有重復(fù)字符的情況，不重復(fù)的字符各有兩種狀態(tài)；而重復(fù)的字符狀態(tài)個(gè)數(shù)與重復(fù)次數(shù)有關(guān)。以a,a,b為例，b有兩種狀態(tài)：被選中、不被選中，a,a有三種狀態(tài)：被選中2個(gè)，被選中1個(gè)，不被選中。2*3=6，排除為空的情況，一共有5種組合：

a(被選中2個(gè))b(被選中)                 =>    aab
a(被選中2個(gè))b(不被選中)               =>    aa
a(被選中1個(gè))b(被選中)                 =>    ab
a(被選中1個(gè))b(不被選中)               =>    a
a(不被選中)b(被選中)                  =>    b
a(不被選中)b(不被選中)                =>    空(不作為一種組合情況)

上述無(wú)重復(fù)字符的情況可以看作是有重復(fù)字符的情況的特例，因此，僅實(shí)現(xiàn)有重復(fù)字符的字符串組合處理思路即可。

package chapter4;
import java.util.*;
/**
 * Created by ryder on 2017/7/22.
 * 字符串的組合
 */
public class P199_StringCombination {
    //無(wú)重復(fù)字符：對(duì)于每一個(gè)字符，都由兩種選擇：被選中、不被選中；
    //有重復(fù)字符：整體需要先排序，對(duì)于重復(fù)n遍的某種字符，有如下選擇：不被選中，選1個(gè)，選2個(gè)...選n個(gè)。
    public static List<char[]> combination(char[] strs) {
        if (strs == null || strs.length == 0)
            return null;
        Arrays.sort(strs);
        List<char[]> ret = new LinkedList<>();
        combinationCore(strs,ret,new StringBuilder(),0);
        return ret;
    }
    public static void combinationCore(char[] strs,List<char[]> ret,StringBuilder stringBuilder,int cur){
        if(cur==strs.length ) {
            if(stringBuilder.length()>0)
                ret.add(stringBuilder.toString().toCharArray());
        }
        else if(cur+1==strs.length||strs[cur]!=strs[cur+1]){
            combinationCore(strs,ret,stringBuilder.append(strs[cur]),cur+1);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
            combinationCore(strs,ret,stringBuilder,cur+1);

        }
        else{
            //先計(jì)算出重復(fù)次數(shù)
            int dumplicateStart = cur;
            while(cur!=strs.length&&strs[dumplicateStart]==strs[cur]){
                stringBuilder.append(strs[cur]);
                cur++;
            }
            int newStart = cur;
            while (cur>=dumplicateStart) {
                combinationCore(strs, ret, stringBuilder, newStart);
                if(cur!=dumplicateStart)
                    stringBuilder.deleteCharAt(stringBuilder.length() - 1);
                cur--;
            }

        }
    }
    public static void main(String[] args) {
        char[] strs2 = {'a', 'a', 'b'};
        List<char[]> ret2 = combination(strs2);
        for (char[] item : ret2) {
            for (int i = 0; i < item.length; i++)
                System.out.print(item[i]);
            System.out.println();
        }
    }
}

運(yùn)行結(jié)果

aab
aa
ab
a
b