递归生成数组元素组合效率不足，求更高效的实现方案

原递归方案的性能瓶颈主要来自三个方面：

• 递归调用的栈开销，数组元素较多时，栈操作的累积开销不可忽视
• current列表的add/remove操作虽为O(1)，但频繁的方法调用和内部维护会产生额外开销
• 每次递归终止时new ArrayList<>(current)的复制操作，大量组合场景下复制总耗时很高

以下是两种更高效的实现方案：

方法一：位运算迭代法 #

利用每个组合对应一个二进制掩码的特性，直接遍历所有可能的掩码生成组合。完全避免递归开销，同时预先分配集合容量减少动态扩容损耗。

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

public class FastCombinations {
    public static List<List<Integer>> generateCombinations(int[] arr) {
        int n = arr.length;
        int totalCombos = 1 << n; // 计算总组合数：2^n
        // 预先分配结果集合容量，避免多次扩容
        List<List<Integer>> result = new ArrayList<>(totalCombos);
        
        for (int mask = 0; mask < totalCombos; mask++) {
            List<Integer> combo = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                // 检查第i位是否为1，是则加入当前组合
                if ((mask & (1 << i)) != 0) {
                    combo.add(arr[i]);
                }
            }
            result.add(combo);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        List<List<Integer>> combs = generateCombinations(arr);
        System.out.println(combs);
    }
}

优势 #

• 无递归栈开销，执行流程更直接
• 预先分配容量，避免ArrayList动态扩容的性能损耗
• 代码逻辑直观，调试维护成本低

方法二：优化递归实现 #

若偏好递归写法，可通过数组替换List存储临时组合，消除add/remove操作开销，同时预先分配结果集合容量。

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

public class OptimizedRecursiveCombinations {
    public static List<List<Integer>> generateCombinations(int[] arr) {
        int n = arr.length;
        List<List<Integer>> result = new ArrayList<>(1 << n);
        int[] current = new int[n]; // 用数组存储当前组合，避免List的add/remove开销
        generate(arr, 0, current, 0, result);
        return result;
    }

    private static void generate(int[] arr, int index, int[] current, int count, List<List<Integer>> result) {
        if (index == arr.length) {
            List<Integer> combo = new ArrayList<>(count);
            // 复制数组中已选择的元素到List
            for (int i = 0; i < count; i++) {
                combo.add(current[i]);
            }
            result.add(combo);
            return;
        }
        // 选择当前元素：将元素存入数组，count+1
        current[count] = arr[index];
        generate(arr, index + 1, current, count + 1, result);
        // 不选择当前元素：直接递归，count不变
        generate(arr, index + 1, current, count, result);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        List<List<Integer>> combs = generateCombinations(arr);
        System.out.println(combs);
    }
}

优势 #

• 用数组代替List存储临时组合，消除了add/remove的方法调用开销
• 预先分配结果集合容量，减少扩容损耗
• 保留递归逻辑结构，适合习惯递归思维的场景

注意事项 #

当数组元素数量n超过20时，总组合数2^n会突破100万，继续生成所有组合会占用大量内存和时间。此时需重新评估业务需求，考虑剪枝、按需生成等替代方案。

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