如何从初始数组生成所有子数组？递归问题修正与最优算法

错误原因分析 #

1. 空数组的产生 #

原代码中，当start == end时，else分支里的循环for (int i = start; i < end; i++)不会执行，直接添加了空列表。比如初始调用generateAllSubArrays(nums, list, 0, 0)时，就生成了第一个空数组。

2. 子数组缺失与冗余 #

原逻辑存在两处核心问题：

• 递归过程中，当start > end时递归end+1，但每次end递增后，start从0重新开始，会在start == end时重复生成空数组，挤占有效子数组的位置；
• 原代码生成的子数组是[start, end-1]区间，而预期的子数组是[start, end]闭区间，导致部分子数组重复、部分长数组生成逻辑混乱，最终出现缺失。

修正后的递归代码 #

调整逻辑，确保只生成非空连续子数组，遍历所有start <= end的有效区间：

List<List<Integer>> list = new ArrayList<>();
generateAllSubArrays(nums, list, 0);

private void generateAllSubArrays(int[] nums, List<List<Integer>> list, int start) {
    // 起始位置超出数组范围则终止递归
    if (start >= nums.length) {
        return;
    }
    // 从当前start出发，遍历所有可能的结束位置
    List<Integer> current = new ArrayList<>();
    for (int end = start; end < nums.length; end++) {
        current.add(nums[end]);
        // 复制当前子数组并加入结果集
        list.add(new ArrayList<>(current));
    }
    // 递归处理下一个起始位置
    generateAllSubArrays(nums, list, start + 1);
}

测试输入[1,1,1,1]，输出包含所有预期子数组（顺序与预期略有差异，若需严格匹配预期顺序，可调整为固定end遍历start从0到end）：

[[1], [1,1], [1,1,1], [1,1,1,1], [1], [1,1], [1,1,1], [1], [1,1], [1]]

时间与空间复杂度最优算法 #

生成所有子数组的总数量为n*(n+1)/2（n为数组长度），这是理论下界，因此最优算法的时间复杂度为O(n²)，空间复杂度为O(n²)（存储所有子数组）。

迭代式双重循环实现更高效（避免递归栈开销）：

public List<List<Integer>> generateAllSubArrays(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    int n = nums.length;
    for (int start = 0; start < n; start++) {
        List<Integer> current = new ArrayList<>();
        for (int end = start; end < n; end++) {
            current.add(nums[end]);
            result.add(new ArrayList<>(current));
        }
    }
    return result;
}

该算法直接遍历所有起始位置start，对每个start遍历所有可能的结束位置end，逐步构建子数组并添加到结果中，逻辑清晰且无冗余操作。

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