《剑指offer第二版》面试题38_1：字符串的组合（java）

题目描述

• 输入一个字符串，打印出该字符串的所有组合，例如输入字符串abc，则所有的排列为：a、b、c、ab、ac、bc、abc。

解题思路：

1. 如果输入n个字符，则能构成长度为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 字符数组
 * @param begine 从chars中第begin个字符开始选择m个字符进行组合
 * @param prefix 存放组合的结果
 * @param m 组合的字符的长度
 */
void rCombination(char[] chars, int begine, StringBuilder prefix, int m){
    if (m <= 0 ) {
        // 还需选取0个字符，表示组合完成，打印结果
        System.out.println(prefix);
        return;
    }
    if (begine >= chars.length) {
        // 达到边界情况，防止后面数组越界
        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);
}