Java如何基于给定字符生成指定长度的所有可重复字符组合

该需求本质是求输入字符集的k次笛卡尔积，其中k等于输入字符串的长度，将每一组元素拼接为字符串即可得到目标结果。你可以根据自己的场景选择回溯递归或者迭代两种实现方式：

• 回溯递归逻辑简洁易扩展，适合输入字符串长度较短的场景
• 迭代实现避免了递归栈溢出风险，适合输入长度较高的场景

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

public class CombinationGenerator {
    public static List<String> generateEqualLengthCombinations(String input) {
        List<String> result = new ArrayList<>();
        if (input.isEmpty()) {
            return result;
        }
        char[] charSet = input.toCharArray();
        backtrack(result, charSet, new StringBuilder(), input.length());
        return result;
    }

    private static void backtrack(List<String> result, char[] charSet, StringBuilder current, int targetLen) {
        // 当前拼接字符串达到目标长度，加入结果集
        if (current.length() == targetLen) {
            result.add(current.toString());
            return;
        }
        // 遍历所有可选字符拼接后递归
        for (char c : charSet) {
            current.append(c);
            backtrack(result, charSet, current, targetLen);
            // 回溯删除最后一位字符
            current.deleteCharAt(current.length() - 1);
        }
    }

    public static void main(String[] args) {
        // 测试输入"abc"，会输出27个符合要求的字符串
        List<String> combinations = generateEqualLengthCombinations("abc");
        combinations.forEach(System.out::println);
    }
}

• 如果输入字符串存在重复字符，可先对字符集去重，避免生成重复组合，去重代码示例：

// 替换原有charSet生成逻辑即可
char[] charSet = input.chars()
        .distinct()
        .mapToObj(c -> (char) c)
        .collect(StringBuilder::new, StringBuilder::append, StringBuilder::append)
        .toString()
        .toCharArray();

• 迭代实现版本参考：

public static List<String> generateIterative(String input) {
    List<String> result = new ArrayList<>();
    if (input.isEmpty()) {
        return result;
    }
    char[] charSet = input.toCharArray();
    int targetLen = input.length();
    result.add("");
    for (int i = 0; i < targetLen; i++) {
        List<String> temp = new ArrayList<>();
        for (String s : result) {
            for (char c : charSet) {
                temp.add(s + c);
            }
        }
        result = temp;
    }
    return result;
}

• 整体时间复杂度为O(m^n)，其中m是字符集大小，n是输入字符串长度，属于指数级复杂度，输入过长时会出现性能下降。

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