题目来源 《剑指offer》

01 题目描述

给一个字符串如 "abc",请输出它的全组合。如 "abc"的全组合。a,b,c,ab,ac,bc,abc。

02 题解

小伙伴们组合的概念不懂的话可以自行百度哦~

这道题，我们直接与递归的逻辑对比怎么回事。

如果有四个字符串 abcd，数组长度为arrLength=4；输出字符长度为resultLength；

char []result=new char[resultLength];

• 求resultLength=1的组合时，直接循环输出a,b,c,d即可。

result[0]='a'， result.length == resultLength 输出

result[0]='b'， result.length == resultLength 输出

result[0]='c'， result.length == resultLength 输出

result[0]='d'， result.length == resultLength 输出

• 求resultLength=2的组合,

第一个字符取startIndex=0的a。a可以与 {b,c,d} 下标{1,2,3}组成组合，得结果 ab,ac, ad。

char []result=new char[resultLength];

result[0]='a', result[1]='b' result.length==resultLength 输出

result[0]='a', result[1]='c' result.length==resultLength 输出

result[0]='a', result[1]='d' result.length==resultLength 输出

第一个字符取startIndex=1的b，b可以与剩余的 {c,d} 下标{2,3}组成组合，得结果 bc,bd。

result[0]='b', result[1]='c' result.length==resultLength 输出

result[0]='b', result[1]='d' result.length==resultLength 输出

第一个字符取startIndex=2的c，c可以与{d}下标{3}组合， 得结果 cd。

result[0]='c', result[1]='d' result.length==resultLength 输出

（3）求长度为3的组合 abcd

abc，abd，acd的由来

result[0]='a', result[1]='b' ,result[1]='c' , result.length==resultLength 输出

result[0]='a', result[1]='c' ,result[1]='d' , result.length==resultLength 输出

result[0]='b', result[1]='c' ,result[1]='d' , result.length==resultLength 输出

bcd的由来。

03 代码和总结

• 其中result[0] result[1]，result[....]等分别在不同的递归层次。
• result[.....]等在可以访问的范围内取值。

比如 resultLength=2时

(1)result[0]的取值范围是{abcd}中的 {'a'(0),'b'(1),'c'(2)}。

大于等于startIndex=0。 小于等于 (arrLength-charLength)即2.

result[0]取'a'(0)时，result[1]的范围是{bcd} {1,2,3} 。

范围result1的范围是 大于等于startIndex = (result0+1)=1

小于等于[(arrLength-charLength)即2 + resultIndex] 为2;

（2)result[0]='b'（1下标）时

范围result[1]的范围是 大于等于startIndex = (result0+1)=2

小于等于[(arrLength-charLength)即2 + resultIndex(1)]=3;

代码

public static void main(String[] args) {
 String str = "abcd";
 printLetterCombine(str);
 System.out.println(count);
}
public static void printLetterCombine(String str) {
 if (str == null || str.length() == 0) {
 return;
 }
 int n = str.length();
 for (int resultLength = 1; resultLength <= n; resultLength++) { // 长度为1到n的组合
 char[] s = new char[resultLength]; // 生命长度为resultLength的数组。
 getLetterCombine(s, 0, 0, resultLength, str);
 }
}
// 每一个递归的层次计算一个值 
public static void getLetterCombine(char[] result, int resultIndex, int startIndex, int resultLength, String str) {
 int endIndex = str.length() - resultLength + resultIndex;
 for (int i = startIndex; i <= endIndex; i++) {
 result[resultIndex] = str.charAt(i);
 if (resultIndex == resultLength - 1) {
 System.out.println(Arrays.toString(result));
 count++;
 continue;
 }
 getLetterCombine(result, resultIndex + 1, i + 1, resultLength, str);
 }
}