生成所有将长度为 n 的数组划分为恰好 k 个连续非空子数组的组合，可以通过递归或迭代的方式实现。以下是具体的思路和代码示例：思路解析要将一个长度为 n 的数组

本文讲解如何系统性地生成一个长度为 n 的数组的所有恰好 k 段连续子数组划分方案，核心思路是枚举 k−1 个合法分割点（即在 n−1 个可选间隙中选 k−1 个），并提供清晰、正确、可复用的 Java 实现。

该问题本质是组合数学中的分段计数问题：给定一个含 n 个连续元素的数组（如 [1,2,3,4,5,6]），要求将其唯一地划分为 k 个非空、相邻、不重叠的子数组（例如 [[1], [2,3], [4,5,6]]），且所有子数组必须保持原始顺序与连续性。

✅ 正确建模：从“分割点”出发

关键直觉在于：

• 一个长度为 n 的数组有 n−1 个可插入分割符的位置（即元素之间的间隙）：
  1 | 2 | 3 | 4 | 5 | 6 → 5 个间隙（索引位置：1, 2, 3, 4, 5，对应“在第 i 个元素后切”）。
• 要得到 恰好 k 个子数组，需且仅需选择 k−1 个互不相同、有序的分割位置（无需“非相邻”额外检查——因为间隙天然离散，选不同位置即自动满足子数组非空）。
• 因此总方案数为组合数：
  $$\binom{n-1}{k-1}$$
  对 n=6, k=3，即 $\binom{5}{2} = 10$，与预期一致。

⚠️ 注意：原问题约束“子数组至少 1 元素”已由“在间隙处切割”天然保证；“连续性”由子数组取 subList(start, end) 严格保障。

❌ 原递归代码的主要缺陷分析

你提供的 Java 递归实现存在以下关键逻辑错误：

1. 状态污染严重：eachSubArray.clear() 在循环内调用，导致上层递归残留数据被清空，破坏回溯一致性；
2. 剪枝条件错误：if(k==0 || index==arr.length) return; 过早终止，未处理 k==1 但 index < arr.length 的合法情况；
3. 子数组构造混乱：在 for 循环中不断 add(arr[i]) 到 eachSubArray，却未在每次递归前克隆，导致多个结果共享同一引用；
4. 边界处理缺失：未确保 k-1 个分割点严格递增且位于 [1, n-1] 范围内，易生成越界或重复划分。

这些问题共同导致输出缺失、重复或格式错乱（如出现 [1,2,3,4,5,6] 单段，或 [1,3] 等非法非连续子数组）。

✅ 推荐解法：组合枚举 + 线性切分（清晰、高效、无副作用）

我们采用两阶段策略：

1. 生成所有 k−1 元组合：从 {1, 2, ..., n−1} 中选出严格递增的 k−1 个分割位置（如 n=6, k=3 → 从 {1,2,3,4,5} 选 2 个）；
2. 按分割点线性切分：将数组依序切为 k 段，每段为 arr[start..end)。

以下是修复后的完整 Java 实现（含详细注释）：

import java.util.*;

public class ArrayPartitionGenerator {

    /**
     * 生成长度为 n 的自然数数组 [1,2,...,n] 的所有恰好 k 段连续子数组划分
     * @param n 数组长度
     * @param k 子数组段数
     * @return 三维列表：List<List<List<Integer>>>
     */
    public static List<List<List<Integer>>> generatePartitions(int n, int k) {
        if (k <= 0 || k > n) return Collections.emptyList();

        // 构造源数组 [1, 2, ..., n]
        List<Integer> arr = new ArrayList<>();
        for (int i = 1; i <= n; i++) arr.add(i);

        // 所有可能的分割位置：在索引 1~n-1 后切（即切在第 i 个元素之后）
        List<Integer> splitCandidates = new ArrayList<>();
        for (int i = 1; i < n; i++) splitCandidates.add(i);

        List<List<List<Integer>>> result = new ArrayList<>();
        // 生成所有 C(n-1, k-1) 种分割点组合
        List<List<Integer>> allSplitCombinations = generateCombinations(splitCandidates, k - 1);

        for (List<Integer> splits : allSplitCombinations) {
            List<List<Integer>> partition = new ArrayList<>();
            int start = 0;
            // 按升序分割点依次切分
            for (int end : splits) {
                partition.add(new ArrayList<>(arr.subList(start, end)));
                start = end;
            }
            // 添加最后一段
            partition.add(new ArrayList<>(arr.subList(start, n)));
            result.add(partition);
        }

        return result;
    }

    // 辅助方法：生成 list 中所有 size 元素的组合（无重复、有序）
    private static List<List<Integer>> generateCombinations(List<Integer> list, int size) {
        List<List<Integer>> result = new ArrayList<>();
        combine(list, size, 0, new ArrayList<>(), result);
        return result;
    }

    private static void combine(List<Integer> list, int size, int start,
                                List<Integer> current, List<List<Integer>> result) {
        if (current.size() == size) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i <= list.size() - (size - current.size()); i++) {
            current.add(list.get(i));
            combine(list, size, i + 1, current, result);
            current.remove(current.size() - 1);
        }
    }

    // 示例主函数
    public static void main(String[] args) {
        int n = 6, k = 3;
        List<List<List<Integer>>> partitions = generatePartitions(n, k);

        System.out.println("Total partitions: " + partitions.size());
        for (int i = 0; i < partitions.size(); i++) {
            System.out.printf("Combination %d: %s%n", i + 1, partitions.get(i));
        }
    }
}

✅ 输出验证（与题目完全一致）

运行上述代码，输出 10 种划分，顺序与题目示例一致（注意：组合生成顺序依赖 generateCombinations 的字典序，可通过 Collections.sort() 预处理候选集确保稳定）：

Combination 1: [[1], [2], [3, 4, 5, 6]]
Combination 2: [[1], [2, 3], [4, 5, 6]]
...
Combination 10: [[1, 2, 3, 4], [5], [6]]

? 关键优势总结

• 正确性保障：基于组合数学严格建模，无递归状态干扰；
• 时间复杂度最优：$\mathcal{O}\left(\binom{n-1}{k-1} \cdot n\right)$，与理论下界匹配；
• 内存安全：所有 ArrayList 均显式 new，避免引用共享；
• 高可扩展性：轻松适配任意 int[] 输入（只需替换 arr 构造逻辑）；
• 零依赖：纯 JDK 实现，无需第三方库。

? 提示：若需支持自定义数组（如 int[] input），只需将 arr 初始化改为 Arrays.stream(input).boxed().collect(Collectors.toList())，其余逻辑完全复用。

掌握“分割点组合”这一建模范式，不仅能解决本题，还可推广至：子数组和约束、动态规划状态划分、字符串分词等经典场景。