Java中如何将排列生成代码改造为不考虑顺序的组合生成代码

组合和排列的核心差异是不需要考虑元素的顺序，所以要避免生成"AB"和"BA"这类重复结果。最高效的实现方式是通过下标约束选取范围，每次选取字符时只从当前位置的后一位开始选，永远不回头选取已经遍历过的字符，天然保证组合元素的顺序和原字符串一致，不需要额外去重步骤，时间复杂度为最优的O(2^n)（n为字符串长度）。

public class Combination {
    public static void main (String[] args) {
        // 生成字符串"ABCD"的所有长度的组合
        combine("ABCD");
        // 如果需要生成指定长度的组合，比如长度为2的，调用combine("ABCD", 2)即可
    }

    // 对外暴露的生成所有长度组合的方法
    public static void combine(String full) {
        if (full == null || full.length() == 0) {
            System.out.println("You must provide a string of length > 0");
            return;
        }
        combine("", full, 0);
    }

    // 对外暴露的生成指定长度组合的方法
    public static void combine(String full, int targetLength) {
        if (full == null || full.length() == 0 || targetLength <= 0 || targetLength > full.length()) {
            System.out.println("Invalid input parameters");
            return;
        }
        combine("", full, 0, targetLength);
    }

    // 生成所有长度组合的递归实现
    private static void combine(String prefix, String full, int start) {
        // 每一层递归的prefix本身就是一个合法组合，直接输出
        if (prefix.length() > 0) {
            System.out.println(prefix);
        }
        for (int i = start; i < full.length(); i++) {
            // 下一层递归从i+1的位置开始选，避免重复
            combine(prefix + full.charAt(i), full, i + 1);
        }
    }

    // 生成指定长度组合的递归实现
    private static void combine(String prefix, String full, int start, int targetLength) {
        if (prefix.length() == targetLength) {
            System.out.println(prefix);
            return;
        }
        // 剪枝优化：剩余可选字符数不足需要的字符数时直接终止循环
        for (int i = start; i <= full.length() - (targetLength - prefix.length()); i++) {
            combine(prefix + full.charAt(i), full, i + 1, targetLength);
        }
    }
}

• 去掉了原排列逻辑中拼接剩余字符串的操作，改用start下标标记下一层递归的起始选取位置，大幅降低字符串拼接的性能开销
• 所有组合的元素顺序和原字符串保持一致，从根源上避免了重复组合的生成，不需要额外的去重逻辑
• 新增了剪枝逻辑：生成指定长度组合时，当剩余可选字符数量小于还需要选取的字符数量时，直接终止循环，进一步提升效率

如果采用先生成全排列再按排序后去重的方式实现组合，时间复杂度为O(n! * n)，当字符串长度大于10时性能会急剧下降，而本实现的时间复杂度为O(2^n)，且没有额外的去重、排序开销，是组合生成的最优方案。

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