題目描述
- 輸入一個字符串，打印出該字符串的所有組合悔捶，例如輸入字符串a(chǎn)bc铃慷，則所有的排列為：a、b蜕该、c犁柜、ab、ac堂淡、bc馋缅、abc扒腕。
解題思路：
- 如果輸入n個字符，則能構(gòu)成長度為1,2,...n的組合萤悴。
- 求n個字符中長度為m的組合的時候瘾腰，可以把n個字符分為兩個部分，第一部分：第一個字符覆履，第二部分：n-1個其他的所有字符蹋盆。
- 可以選取第一個字符，再在第二部分的字符里選取m-1個字符硝全，也可以不選取第一個字符栖雾，在第二部分選取m個字符。
- 即求n個字符串中長度為m的組合的時候伟众，可以分解為兩個子問題：n-1個字符里求長度為m-1的組合析藕；n-1個字符里求長度為m的組合。
- 通過遞歸解決凳厢。
代碼
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個字符進行組合
* @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) {
// 達到邊界情況数初，防止后面數(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);
}
