這個(gè)我想到高中的排列組合，用的是隔板法(不太記得是不是叫這個(gè))。比如，隔板是說(shuō)在1|2|3|4數(shù)字中間放的分隔板。分成一個(gè)集合，不用隔板分成兩個(gè)集合，放一個(gè)隔板，共C(n-1,1),比如{1|234}{12|34}{123|4}分成k個(gè)集合，放k-1個(gè)隔板，共C(n-1,k-1)種。然后想如何實(shí)現(xiàn)隔板，給隔板編號(hào)1,2,...,n-1于是每次放k個(gè)隔板意味著從n-1個(gè)數(shù)中取出k個(gè)數(shù)字，就是組合數(shù)，可以用回溯遍歷出來(lái)seq[]放k的數(shù)字seq[]=-1表示這個(gè)位置沒(méi)有數(shù)字DFS(index){if(index==k){print();return;}for(inti=1;i<=n-1;++i){if(seq[index]==-1){seq[index]=i;//DFS(index+1)seq[index]=-1}}}print(){intindex=0;for(inti=1;i<=n;++i){printf(i);if(i==seq[index]){index++;print(|)}}}DFS(1)講的好，如果不存儲(chǔ)全部的子集的話，每次維護(hù)/保存當(dāng)前i的子集的序列，每次加一個(gè)i+1時(shí)，只需要輸出i，和將i加到當(dāng)前序列里面就可以了。DFS(intnum){print({num});for(inti=0;iseq[i].add(num);//把num加入當(dāng)前隊(duì)列print({);//便于顯示觀看for(intj=0;jprinf(seq[i][j]);prinf(});//便于顯示觀看}DFS(num+1);}如果不存儲(chǔ)全部的子集的話,只需要復(fù)制seq，再添加num到其中一個(gè)seq中去即可，再加一個(gè){num}。咦？其實(shí)這個(gè)也可以直接一個(gè)循環(huán)，不用DFS還要浪費(fèi)棧，因?yàn)閚um是從1到n沒(méi)有變化的呀！for(intnum=1;num<=n;++num){print({num});for(inti=0;iseq[i].add(num);//把num加入當(dāng)前隊(duì)列print({);//便于顯示觀看for(intj=0;jprinf(seq[i][j]);prinf(});//便于顯示觀看}}
