求实现数组n个有序子集全划分的函数算法（保持原数组顺序）

我来帮你搞定这个有序数组划分的问题！这个需求的核心是在严格保持原数组元素顺序的前提下，生成所有将数组拆分为n个非空子集的组合，用递归回溯的思路就能很好地实现。

先明确下需求：我们要实现一个函数，输入数组arr和整数n（n <= arr.length），返回所有将arr划分为n个非空子集的方式，且每个子集里的元素顺序必须和原数组完全一致，最终结果是一个三维数组（数组套数组套数组）。

比如题目给出的示例：

• func([1, 2, 3], 1) → [[[1, 2, 3]]]（只有一种方式，整个数组作为唯一子集）
• func([1, 2, 3], 2) → [[[1],[2, 3]], [[1, 2],[3]]]（两种划分方式）
• func([1, 2, 3], 3) → [[[1], [2], [3]]]（每个元素单独成子集）

这个问题用递归回溯的思路最直观，核心是逐步确定每个子集的边界，同时保证剩余元素能被划分成剩下的子集数：

1. 终止条件：
   • 当n = 1时，直接返回包含整个数组的三维数组（因为只能把所有元素放在一个子集里）
   • 当n = arr.length时，返回每个元素单独作为子集的三维数组（每个子集只能有一个元素）
2. 递归过程：
   • 遍历所有可能的第一个子集的结束位置：第一个子集可以从数组开头取1个、2个……直到剩下的元素数量足够分成n-1个非空子集（也就是第一个子集最多取arr.length - (n-1)个元素，保证剩下的元素至少能每个子集分一个）
   • 对剩下的元素递归调用函数，生成划分成n-1个子集的所有结果
   • 将第一个子集和递归得到的每个结果组合，收集所有可能的划分方式

function func(arr, n) {
    // 处理边界情况
    if (n === 1) {
        return [[arr.slice()]];
    }
    if (n === arr.length) {
        return [arr.map(num => [num])];
    }
    
    const result = [];
    // 循环确定第一个子集的长度，确保剩余元素能分成n-1个非空子集
    for (let i = 1; i <= arr.length - (n - 1); i++) {
        // 切分第一个子集（用slice避免修改原数组）
        const firstSubset = arr.slice(0, i);
        // 递归处理剩下的元素，生成n-1个子集的所有划分
        const restPartitions = func(arr.slice(i), n - 1);
        // 将第一个子集和每个递归结果合并，加入总结果
        restPartitions.forEach(partition => {
            result.push([firstSubset, ...partition]);
        });
    }
    return result;
}

// 验证示例
console.log(func([1, 2, 3], 1)); // [[[1,2,3]]]
console.log(func([1, 2, 3], 2)); // [[[1],[2,3]], [[1,2],[3]]]
console.log(func([1, 2, 3], 3)); // [[[1],[2],[3]]]

• 用slice()复制数组片段，避免修改原数组的内容
• 循环边界i <= arr.length - (n-1)是关键：确保剩下的元素数量足够分成n-1个非空子集，不会出现无法划分的情况
• 递归调用后，通过展开运算符...将第一个子集和后续的划分结果合并，生成完整的划分方式

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