Java字符组合生成问题求助：StringBuilder列表字符重复追加

嘿，我完全懂你现在的困扰！你想要生成指定长度的所有字符组合，但程序总是把之前的字符串一直追加到新字符上，导致结果完全不对对吧？这大概率是因为你在递归或者循环过程中没有正确处理字符串的状态——要么复用了可变的字符串对象却没做回溯，要么没创建独立的字符串实例。

先看常见的错误原因（模拟你可能的写法） #

比如很多新手会用StringBuilder来拼接，但忘记在递归结束后撤销追加的操作：

// 错误示例：未做回溯导致的追加问题
public class WrongCombinationGenerator {
    private static void generate(String chars, int length, StringBuilder current) {
        if (current.length() == length) {
            System.out.println(current);
            return;
        }
        for (char c : chars.toCharArray()) {
            current.append(c);
            generate(chars, length, current);
            // 这里没有删除最后追加的字符！导致回溯时current带着之前的内容
        }
    }

    public static void main(String[] args) {
        generate("abc", 2, new StringBuilder());
    }
}

运行这个会输出aa、aab、aabc这类错误结果，因为每次递归回来后，StringBuilder还保留着上一次追加的字符。

两种正确的解决方案 #

方案1：用不可变String（简单易上手，适合新手）

String是不可变的，每次用+拼接都会创建新的字符串实例，这样每个递归分支的字符串都是独立的，不会互相干扰：

package com.practice.programs;

public class CombinationGenerator {
    // 递归生成组合
    private static void generateCombinations(String charSet, int targetLength, String current) {
        // 终止条件：当前字符串长度达标，输出结果
        if (current.length() == targetLength) {
            System.out.println(current);
            return;
        }
        // 遍历每个字符，拼接后进入下一层递归
        for (char c : charSet.toCharArray()) {
            generateCombinations(charSet, targetLength, current + c);
        }
    }

    public static void main(String[] args) {
        String charSet = "abc";
        int combinationLength = 2;
        // 初始传入空字符串开始生成
        generateCombinations(charSet, combinationLength, "");
    }
}

运行这个就能得到你想要的aa、ab、ac、ba、bb、bc、ca、cb、cc啦！

方案2：用StringBuilder+手动回溯（效率更高）

如果字符集或目标长度很大，String的频繁创建会有点低效，这时候可以用StringBuilder，但一定要记得回溯——在递归结束后删除最后追加的字符，恢复到之前的状态：

package com.practice.programs;

public class CombinationGenerator {
    private static void generateCombinations(String charSet, int targetLength, StringBuilder current) {
        if (current.length() == targetLength) {
            System.out.println(current);
            return;
        }
        for (char c : charSet.toCharArray()) {
            current.append(c);
            generateCombinations(charSet, targetLength, current);
            // 回溯：删掉最后一个字符，回到上一轮的状态
            current.deleteCharAt(current.length() - 1);
        }
    }

    public static void main(String[] args) {
        String charSet = "abc";
        int combinationLength = 2;
        generateCombinations(charSet, combinationLength, new StringBuilder());
    }
}

方案3：迭代写法（不用递归，新手更容易理解）

如果你对递归不太熟悉，也可以用循环一步步构建组合：

package com.practice.programs;

import java.util.ArrayList;
import java.util.List;

public class CombinationGenerator {
    public static List<String> generateIteratively(String charSet, int targetLength) {
        List<String> combinations = new ArrayList<>();
        // 先初始化长度为1的所有组合
        for (char c : charSet.toCharArray()) {
            combinations.add(String.valueOf(c));
        }
        // 循环生成更长的组合，直到达到目标长度
        for (int i = 2; i <= targetLength; i++) {
            List<String> temp = new ArrayList<>();
            // 把现有每个组合和字符集中的每个字符拼接
            for (String s : combinations) {
                for (char c : charSet.toCharArray()) {
                    temp.add(s + c);
                }
            }
            combinations = temp;
        }
        return combinations;
    }

    public static void main(String[] args) {
        String charSet = "abc";
        int combinationLength = 2;
        List<String> result = generateIteratively(charSet, combinationLength);
        for (String s : result) {
            System.out.println(s);
        }
    }
}

问题根源总结 #

你之前的程序出错，核心就是复用了可变的字符串对象却没有管理好它的状态——比如用StringBuilder一直追加，却没在每次分支结束后恢复原状。解决的关键就是保证每个组合分支的字符串是独立的：要么用不可变String自动创建新实例，要么用可变对象时手动回溯。

内容的提问来源于stack exchange，提问作者Amit Gawali