將長度為n的數(shù)組分隔成m個子數(shù)組，可以看作是將m-1個分隔符插入原來數(shù)組的n-1個位置中，所以我們只需要求出這m-1個分隔符在原來數(shù)組中的下標(biāo)索引，即可得到子數(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ù)字可以當(dāng)成分隔符在原數(shù)組中的位置勉耀，比如[1,2]表示我們分別在nums[1]和nums[2]左邊插入分隔符指煎，將其分成3份。
