將長度為n的數(shù)組分隔成m個子數(shù)組，可以看作是將m-1個分隔符插入原來數(shù)組的n-1個位置中，所以我們只需要求出這m-1個分隔符在原來數(shù)組中的下標索引，即可得到子數(shù)組的所有情形。所以問題就轉(zhuǎn)換成在n-1個 位置中尋找m-1個分隔符，一共有C_(n-1)(m-1)種情況，我們采用回溯法來生成所有情形：

import java.util.ArrayList;
import java.util.List;

/*
 把一個長度為n的數(shù)組分成m份的所有情況(n>=m)
 本質(zhì)上是將m-1個分隔符插在n-1個不同的位置
 */
public class test{
    static ArrayList<Integer> path = new ArrayList<>();
    static ArrayList<List<Integer>> ans = new ArrayList<>();

    public static void main(String[] args) {
        int m = 3;
        int n = 5;
        insert(0,n-1,m-1);
        System.out.println(ans);
    }
// 這里jindu用來記錄前面分好的部分，res_n表示剩下的可以插的位置數(shù)，res_m表示剩下的分隔符數(shù)量。
    static void insert(int jindu,int res_n,int res_m){
        if(res_m==0){
            ans.add(new ArrayList<>(path));
            return;
        }
        if(res_n < res_m) {
            return;
        }else if(res_m==res_n) {
            for (int i = 0; i <res_m; i++) {
                path.add(jindu+i+1);
            }
            ans.add(new ArrayList<>(path));
        }else{
            for (int i = 0; i <res_n; i++) {
                path.add(jindu+i+1);
                insert(jindu+i+1,res_n-i-1,res_m-1);
                path.remove(path.size()-1);
            }
        }
    }
}

如果我們令m=3，n=5的話，輸出就是

image.png

這里的每個數(shù)字可以當成分隔符在原數(shù)組中的位置，比如[1,2]表示我們分別在nums[1]和nums[2]左邊插入分隔符，將其分成3份。