数组划分为k个连续非空子数组的所有组合生成及递归代码修正

这是一个组合数学问题：需要将长度为n的数组划分为恰好k个连续非空子数组。核心逻辑是：数组共有n-1个可划分的间隙位置，只需从中选择k-1个作为划分点，总组合数为组合数C(n-1, k-1)。例如数组{1,2,3,4,5,6}（n=6，k=3）时，总共有C(5,2)=10种划分方式，预期输出是包含所有划分结果的三维数组。

约束条件 #

• 子数组至少包含1个元素
• 子数组必须由连续元素组成

我尝试用递归方法实现，但结果错误，需要先明确正确的解题思路与直觉，再修正代码并指出错误。

原代码 #

public static void main(String[] args) {
    int n = 6;
    int k = 3;
    int[] arr = new int[]{1,2,3,4,5,6};
    ArrayList<ArrayList<ArrayList<Integer>>> result = new ArrayList<ArrayList<ArrayList<Integer>>>();
    ArrayList<ArrayList<Integer>> eachComb = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> eachSubArray = new ArrayList<Integer>();
    int index = 0;
    
    generateCombinations(arr, k, index, eachSubArray, eachComb, result);
    
    for (ArrayList<ArrayList<Integer>> each : result) {
        for(ArrayList<Integer> eachh: each) {
            System.out.println(eachh);
        }
        System.out.println("-------------------------------");
    }
}

private static void generateCombinations(int[] arr, int k, int index, ArrayList<Integer> eachSubArray,
        ArrayList<ArrayList<Integer>> eachComb, ArrayList<ArrayList<ArrayList<Integer>>> result) {
    

    if(k==0 || index==arr.length) {
        return;
    }
    

    if(!eachSubArray.isEmpty()) {
        eachComb.add(new ArrayList<>(eachSubArray));
    }
    
    if(k==1) {
        ArrayList<Integer> last = new ArrayList<Integer>();
        for(int i=index; i<arr.length; i++) {
            last.add(arr[i]);
        }
        if(!last.isEmpty()) {
            eachComb.add((last));
            result.add(new ArrayList<ArrayList<Integer>>(eachComb));
            eachComb.remove(eachComb.size()-1);
        }
        return;
    }
    
    eachSubArray.clear();
    
    
    
    for(int i=index; i<arr.length; i++) {
        eachSubArray.add((arr[i]));
        generateCombinations(arr, k-1, i+1, eachSubArray, eachComb, result);
        if(!eachComb.isEmpty()) {
            eachComb.remove(eachComb.size()-1);
        }
    }
    
}

原代码错误分析 #

1. 子数组状态管理错误：递归过程中复用同一个eachSubArray引用，且在循环前调用eachSubArray.clear()，会导致之前构建的子数组数据丢失；回溯时没有恢复eachSubArray的状态，导致后续子数组构建混乱。
2. 子数组添加时机错误：递归开头就将非空的eachSubArray加入eachComb，会导致重复添加或错误的子数组被纳入当前组合。
3. 边界条件处理不当：当k==0或index==arr.length直接返回，未处理剩余元素的收尾逻辑；k==1时添加最后一个子数组后，没有清理之前错误加入eachComb的元素。
4. 回溯逻辑不完整：循环中递归返回后仅移除eachComb的最后元素，但未对应恢复eachSubArray的内容，导致后续循环的子数组构建错误。

正确解题思路 #

递归的核心是逐步确定每个子数组的结束位置：

• 从当前索引index开始，遍历所有合法的结束位置：结束位置不能超过arr.length - (k-1)，因为剩余的k-1个子数组每个至少需要1个元素。
• 对每个结束位置，截取当前子数组并加入当前组合，然后递归处理剩余数组（起始索引为结束位置+1，k减1）。
• 当k==1时，直接将当前索引到数组末尾的元素作为最后一个子数组，加入当前组合后将整个组合存入结果集。
• 递归回溯时，要移除当前组合中刚加入的子数组，恢复状态以尝试下一个可能的结束位置。

修正后的代码 #

import java.util.ArrayList;

public class ArrayPartition {
    public static void main(String[] args) {
        int n = 6;
        int k = 3;
        int[] arr = new int[]{1,2,3,4,5,6};
        ArrayList<ArrayList<ArrayList<Integer>>> result = new ArrayList<>();
        
        generateCombinations(arr, k, 0, new ArrayList<>(), result);
        
        for (ArrayList<ArrayList<Integer>> each : result) {
            for(ArrayList<Integer> subArr : each) {
                System.out.println(subArr);
            }
            System.out.println("-------------------------------");
        }
    }

    private static void generateCombinations(int[] arr, int k, int index, 
                                            ArrayList<ArrayList<Integer>> currentComb,
                                            ArrayList<ArrayList<ArrayList<Integer>>> result) {
        // 当k=1时，直接取剩余所有元素作为最后一个子数组
        if (k == 1) {
            ArrayList<Integer> lastSubArr = new ArrayList<>();
            for (int i = index; i < arr.length; i++) {
                lastSubArr.add(arr[i]);
            }
            currentComb.add(lastSubArr);
            result.add(new ArrayList<>(currentComb));
            currentComb.remove(currentComb.size() - 1); // 回溯
            return;
        }

        // 遍历当前子数组的所有可能结束位置，剩余元素至少要能分成k-1个子数组
        for (int i = index; i <= arr.length - k; i++) {
            ArrayList<Integer> subArr = new ArrayList<>();
            for (int j = index; j <= i; j++) {
                subArr.add(arr[j]);
            }
            currentComb.add(subArr);
            // 递归处理剩余部分：起始索引i+1，剩余子数组数量k-1
            generateCombinations(arr, k-1, i+1, currentComb, result);
            currentComb.remove(currentComb.size() - 1); // 回溯
        }
    }
}

代码说明 #

• 简化了参数传递，不再复用单个eachSubArray，而是每次循环都创建新的子数组对象，避免状态混乱。
• 明确了循环的边界：i <= arr.length - k，确保剩余元素足够划分成k-1个子数组。
• 回溯逻辑完整：每次递归返回后，移除当前组合中刚加入的子数组，恢复状态。
• 边界条件处理清晰：k==1时直接处理最后一个子数组，加入结果后立即回溯。

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