生成所有将长度为 n 的数组划分为恰好 k 个连续非空子数组的组合_网络技术

生成所有将长度为 n 的数组划分为恰好 k 个连续非空子数组的组合

发布时间 - 2026-01-26 00:00:00 点击率：次

本文讲解如何系统性地生成一个长度为 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())，其余逻辑完全复用。

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

# java # ai # stream # 高可扩展性 # lsp

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】

上一篇：SQL 使用窗口函数计算滑动平均

下一篇：SQL 如何用递归查询计算组织架构的完整路径字符串

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher

上一篇：SQL 使用窗口函数计算滑动平均

下一篇：SQL 如何用递归查询计算组织架构的完整路径字符串