如何在C#中高效获取将数组拆分为k块的所有可行拆分方案？

要解决将数组拆分为k个满足要求的块的问题，首先明确问题本质：我们需要生成原数组的所有连续拆分方式，拆分为k个非空块，每个块包含连续的数组元素，且所有块覆盖原数组、无重复元素（原数组元素无重复时，连续拆分天然满足无重复要求）。

核心思路 #

对于长度为n的数组，拆分为k个非空块等价于在数组的n-1个元素间隙中选择k-1个位置进行分割。比如长度为5的数组有4个间隙，拆分为3块需要选2个间隙，组合数为C(4,2)=6，正好对应示例中的6种结果。

我们可以通过递归回溯的方式遍历所有合法的分割点组合，生成对应的块列表。

完整实现代码 #

using System;
using System.Collections.Generic;
using System.Linq;

public class ArraySplitter
{
    public static List<IList<IList<int>>> SplitIntoKBlocks(int[] arr, int k)
    {
        var result = new List<IList<IList<int>>>();
        
        // 边界情况处理
        if (k < 1 || k > arr.Length)
            return result;
        
        // 拆分为1块的情况
        if (k == 1)
        {
            result.Add(new List<IList<int>> { arr.ToList() });
            return result;
        }
        
        // 每个元素单独成块的情况
        if (k == arr.Length)
        {
            var blocks = arr.Select(num => new List<int> { num }).Cast<IList<int>>().ToList();
            result.Add(blocks);
            return result;
        }
        
        // 递归回溯生成所有拆分
        Backtrack(0, 0, new List<IList<int>>(), arr, k, result);
        return result;
    }

    private static void Backtrack(int startIndex, int splitsMade, List<IList<int>> currentBlocks, int[] arr, int targetSplits, List<IList<IList<int>>> result)
    {
        // 已完成所有分割，添加最后一块
        if (splitsMade == targetSplits - 1)
        {
            var finalBlock = arr.Skip(startIndex).Take(arr.Length - startIndex).ToList();
            currentBlocks.Add(finalBlock);
            // 存入副本避免后续修改影响结果
            result.Add(currentBlocks.Select(block => block.ToList()).Cast<IList<int>>().ToList());
            // 回溯，移除最后一块
            currentBlocks.RemoveAt(currentBlocks.Count - 1);
            return;
        }

        // 计算当前分割的最大位置：剩余元素需至少能分成 (targetSplits - splitsMade) 块
        int maxSplitPosition = arr.Length - (targetSplits - splitsMade);
        
        for (int i = startIndex + 1; i <= maxSplitPosition; i++)
        {
            // 提取当前块的元素
            var currentBlock = arr.Skip(startIndex).Take(i - startIndex).ToList();
            currentBlocks.Add(currentBlock);
            
            // 递归处理剩余部分
            Backtrack(i, splitsMade + 1, currentBlocks, arr, targetSplits, result);
            
            // 回溯，移除当前块
            currentBlocks.RemoveAt(currentBlocks.Count - 1);
        }
    }

    // 测试示例
    public static void Main()
    {
        int[] arr = { 1, 2, 3, 4, 5 };
        int k = 3;
        var splits = SplitIntoKBlocks(arr, k);
        
        foreach (var split in splits)
        {
            Console.WriteLine($"[{string.Join("], [", split.Select(b => string.Join(", ", b)))}]");
        }
    }
}

代码说明 #

1. 边界处理：先处理k小于1、大于数组长度，以及k=1、k=数组长度的特殊情况，避免无效递归。
2. 递归回溯：
   • startIndex：当前处理的数组起始位置
   • splitsMade：已完成的分割次数
   • currentBlocks：当前正在构建的块列表
   • 每次递归时，计算当前允许的最大分割位置，确保剩余元素能拆分成足够的块
   • 生成当前块后递归处理剩余部分，完成后回溯移除当前块，尝试下一个分割位置
3. 结果存储：每次完成所有分割后，存入当前块列表的副本，避免后续回溯修改已存入的结果。

效率说明 #

该实现的时间复杂度由组合数C(n-1, k-1)决定，这是问题本身的固有复杂度——因为我们需要生成所有可能的拆分结果。在合理的n和k范围内，这个实现是高效的，没有多余的计算开销。

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