本文讲解如何系统性地生成一个长度为 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 递归实现存在以下关键逻辑错误：
- 状态污染严重：eachSubArray.clear() 在循环内调用，导致上层递归残留数据被清空，破坏回溯一致性；
- 剪枝条件错误：if(k==0 || index==arr.length) return; 过早终止，未处理 k==1 但 index
- 子数组构造混乱：在 for 循环中不断 add(arr[i]) 到 eachSubArray，却未在每次递归前克隆，导致多个结果共享同一引用；
- 边界处理缺失：未确保 k-1 个分割点严格递增且位于 [1, n-1] 范围内，易生成越界或重复划分。
这些问题共同导致输出缺失、重复或格式错乱（如出现 [1,2,3,4,5,6] 单段，或 [1,3] 等非法非连续子数组）。
✅ 推荐解法：组合枚举 + 线性切分（清晰、高效、无副作用）
我们采用两阶段策略：
- 生成所有 k−1 元组合：从 {1, 2, ..., n−1} 中选出严格递增的 k−1 个分割位置（如 n=6, k=3 → 从 {1,2,3,4,5} 选 2 个）；
- 按分割点线性切分：将数组依序切为 k 段，每段为 arr[start..end)。
以下是修复后的完整 Java 实现（含详细注释）：
import java.util.*;
public class ArrayPartitionGenerator {
/**
* 生成长度为 n 的自然数数组 [1,2,...,n] 的所有恰好 k 段连续子数组划分
* @param n 数组长度
* @param k 子数组段数
* @return 三维列表：List>>
*/
public static List>> generatePartitions(int n, int k) {
if (k <= 0 || k > n) return Collections.emptyList();
// 构造源数组 [1, 2, ..., n]
List arr = new ArrayList<>();
for (int i = 1; i <= n; i++) arr.add(i);
// 所有可能的分割位置：在索引 1~n-1 后切（即切在第 i 个元素之后）
List splitCandidates = new ArrayList<>();
for (int i = 1; i < n; i++) splitCandidates.add(i);
List>> result = new ArrayList<>();
// 生成所有 C(n-1, k-1) 种分割点组合
List> allSplitCombinations = generateCombinations(splitCandidates, k - 1);
for (List splits : allSplitCombinations) {
List> 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> generateCombinations(List list, int size) {
List> result = new ArrayList<>();
combine(list, size, 0, new ArrayList<>(), result);
return result;
}
private static void combine(List list, int size, int start,
List current, List> 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>> 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())，其余逻辑完全复用。
掌握“分割点组合”这一建模范式，不仅能解决本题，还可推广至：子数组和约束、动态规划状态划分、字符串分词等经典场景。
