題目描述

• 輸入一個字符串，打印出該字符串的所有組合，例如輸入字符串a(chǎn)bc，則所有的排列為：a、b、c、ab、ac、bc、abc。

解題思路：

1. 如果輸入n個字符，則能構(gòu)成長度為1,2,...n的組合。
2. 求n個字符中長度為m的組合的時候，可以把n個字符分為兩個部分，第一部分：第一個字符，第二部分：n-1個其他的所有字符。
3. 可以選取第一個字符，再在第二部分的字符里選取m-1個字符，也可以不選取第一個字符，在第二部分選取m個字符。
4. 即求n個字符串中長度為m的組合的時候，可以分解為兩個子問題：n-1個字符里求長度為m-1的組合；n-1個字符里求長度為m的組合。
5. 通過遞歸解決。

代碼

void combination(char[] chars){
    if (chars == null || chars.length <= 0) {
        return;
    }
    for (int i = 0; i < chars.length; i++) {
        rCombination(chars, 0, new StringBuilder(), i + 1);
    }
}

/**
 * @param chars 字符數(shù)組
 * @param begine 從chars中第begin個字符開始選擇m個字符進(jìn)行組合
 * @param prefix 存放組合的結(jié)果
 * @param m 組合的字符的長度
 */
void rCombination(char[] chars, int begine, StringBuilder prefix, int m){
    if (m <= 0 ) {
        // 還需選取0個字符，表示組合完成，打印結(jié)果
        System.out.println(prefix);
        return;
    }
    if (begine >= chars.length) {
        // 達(dá)到邊界情況，防止后面數(shù)組越界
        return;
    }
    // 1. 選取第一個字符放到prefix中， 再在后面的字符中選擇m-1個字符
    rCombination(chars, begine + 1, prefix.append(chars[begine]), m - 1);
    // 2. 將1中放到prefrex里的字符移除，即不選取第一個字符，再從后面的字符中選取m個字符
    rCombination(chars, begine + 1, prefix.deleteCharAt(prefix.length() - 1), m);
}