這個題其實就是求集合數的具體集合.
如果不是輸出具體集合,而是輸出具體有多少個集合,那麽這題很簡單.
以N=5,K=3為例.C(5,3),5個裏面選3個不重復,計算結果是(5*4*3)/(1*2*3)=10,有10個.
那麽具體列舉出來看看：
（1,2,3）、（1,2,4）、（1,2,5）、（1,3,4）、（1,3,5）、（1,4,5）
（2,3,4）、（2,3,5）、（2,4,5）
（3,4,5）
沒錯,是10個.
這裏註意看,這裏按照第壹個數分隔每壹行,那麽可以看得出來：
如果第壹個是1,那麽就有6個集合
如果第壹個是2（是第壹個數是2,不是含有2）,那麽就有3個集合,
第壹個是3,有1個集合.
6、3、1有沒有什麽規律?具體看看6
6個集合,第壹個是1,那麽就是說,第壹個數已經固定選1了,1已經不用選了,換個說法,就是1已經沒得選了,那麽剩下的情況,就變成是2,3,4,5這4個數裏選2個.
4個數裏選2個,這個好熟悉,不就和當初5個數裏選3個差不多嗎?
那麽計算壹下C（4,2）,(4*3)/(1*2)=6,的確是6；和5個選3個結果是壹樣的.
去看看6、3、1的另外兩個,也是壹樣,3個數裏選2個是3個集合,2個數裏選2個是1個集合.
說到這個,可能已經知道了,C（5,3）=C（4,2）+C（3,2）+C（2,2）
這樣的公式,看起來不就是遞歸嗎?
到這裏,我們可以嘗試換初始值,比如換成是N=7,K=4,那麽結果就是C(7,4)=C(6,3)+C(5,3)+C(4,3)+C(3,3)
看到這個結果,我們可以假設C(N,K) = C(N-1,K-1) + C(N-2,K-1) + ...+ C(K-1,K-1),而條件是K-1>=1
那麽當K==1呢?想想都知道了,N個數裏選1個,結果不就是有N個集合嘛
所以可以得出求集合數的公式
C(N,K) = C(N-1,K-1) + C(N-2,K-1) + ...+ C(K-1,K-1) （K>=2）
C(N,K) = N (K=1)
既然有了公式,遞歸就很好實現了
INT C(N,K){
if(K==1) return N;
else
renturn C(N-1,K-1) + C(N-2,K-1) + ...+ C(K-1,K-1) //用個for或者while就可以了
}
求集合數的思路就是那樣,可問題是要求具體的集合,怎麽辦?
在這裏先設壹個全局數組S[K+1](設K+1可以避免用S[0],便於看代碼思路),用來存具體要輸出的集合.
其實很簡單嘛,既然妳知道了C(N,K) = C(N-1,K-1) + C(N-2,K-1) + ...+ C(K-1,K-1) （K>=2）,那麽C(N-1,K-1) 具體集合的特點是什麽?答案是第壹個數,是1.
既然第壹個數是1,那麽就是S[1] = 1；
然後再來看看,遞歸首先會執行C(N,K) = C(N-1,K-1) + C(N-2,K-1) + ...,而進入了C(N-1,K-1),就會執行C(N-1,K-1) = C(N-2,K-2) + C(N-3,K-2) + ...；那麽就是進入C(N-2,K-2)了,其特點是第二個數,是2,就是S[2] = 2；
壹直這麽下去,知道第壹組出來了,S[K] = K；此時正在C(N-K+1,1)裏面,也就是說,到了最後第K個數要選擇了,之前的K-1個數已經選好了,是1,2,3,4...,K-1,X,X就是第K個要選的數,選了X就可以輸出第壹組集合了.
X有哪些選擇?可看到C(N-K+1,1)其實就是從K,K+1,...,N-1,N這N-K個數裏選壹個作為X.很簡單,用壹個for就可以了,把這N-K個數都選壹遍,輸出集合,那麽久完成了C(N-K+1,1)的任務了.
完成了C(N-K+1,1),接下來是遞歸哪個呢?
倒過來想,C(N-K+1,1)是怎麽出現的呢?
C(N-K+2,2) = C(N-K+1,1)+C(N-K,1)+...+C(1,1).
原來C(N-K+1,1)是這麽來的,所以說,接下來要進入的,是C(N-K,1).
C(N-K,與C(N-K+1,1)有什麽區別?
C(N-K+1,1)是設第K-1個數為K-1,然後去選擇第K個數,
所以C(N-K,1),就是第K-1個數不用K-1了,改為用它的下個數,用K,第K-1個數設為K,
然後繼續for把剩下的K+1到N這N-K-1個數都選壹遍,輸出集合,這樣就完成了C(N-K,1).
做到這裏,具體思路已經90%都出來了,剩下最後的畫龍點睛.
C(N-K-1,1),第K-1個數為K+1,然後從K+2到N裏面選1個.
那麽這裏具體的K-1、K+1、K、K+2、1都是怎麽算出來的呢?
如果已經看懂了思路,那麽其實在妳拿到C(N-K-1,1)時,妳就已經知道“C(N-K-1,1),第K-1個數為K+1,然後從K+2到N裏面選1個.”這句話裏的那些數是怎麽算出來的了.
如果還沒看懂,沒關系,可以先做壹些標記.
把壹開始的遞歸函數,C(N,K)改為C(N,K,A,B,C,D,E)
以N=5,K=3為例,把C(5,3)就是把第0個數設為0,然後從1到5裏選3個數
所以初始的C(5,3)就改寫為C(5,3,0,0,1,5,3).
C（5,3）=C（4,2）+C（3,2）+C（2,2）
那麽C(4,2)就是把第1個數設為1,然後從2到5裏面選2個數,所以C(4,2)改寫為C(4,2,1,1,2,5,2)
C(3,2)就是把第1個數設為2,然後從3到5裏面選2個數,所以C(3,2)改寫為C(4,2,1,2,3,5,2)
C(2,2)就是把第1個數設為3,然後從4到5裏面選2個數,所以C(2,2)改寫為C(4,2,1,3,4,5,2)
看這三個例子,可以發現,A=K全局-K遞歸,B=N全局-N遞歸,C=B+1,D=N全局,E=K遞歸
好咯,剩下的10%也解決了.這題也就完成咯