C(k,n-1)=∏(n-k,n-1)/k!
C(k-1,n-1)=∏(n-k+1,n-1)/(k-1)!
C(k-1,n)+C(k-1,n-1)
=∏(n-k,n-1)/k!+∏(n-k+1,n-1)/(k-1)!
=∏(n-k,n-1)/k!+k·∏(n-k+1,n-1)/k!
=[(n-k)·∏(n-k+1,n-1)!+k·∏(n-k+1,n-1)]/(k-1)!
=[n·∏(n-k+1,n-1)]/k!
=∏(n-k+1,n)]/k!
=C(k,n)
即：C(k-1,n)+C(k-1,n-1)=C(k,n)
說簡單點,就是楊輝三角形的元素算法.
此原理應(yīng)用到你的問題上,重點是：結(jié)果集合的每個元素又是個集合.
若通用集合類Set(其實java中Set就是)；
new Set{value...}為構(gòu)造方法,-{value..}為集合差,+{value...}為集合和,Set(i)和集合第i個元素；
對于n個元素的集合Sn,如果有函數(shù)Set combine(k,Sn),產(chǎn)生n個元素中選k個元素集合的集合；那么,當(dāng)a是n個元素中的任意一個時,combine(k,Sn)=combine(k,Sn-{a})+combine(k-1,Sn-{a}).
由此可以產(chǎn)生遞歸算法：
Set Sn=new Set{a0,a1,...an-1};
Set result=Sn.combine(k,Sn);
.
.
function Set combine(int count,Set S){
if(count==S.size()){
return new Set{S};//這是集合S僅為結(jié)果集的一個元素
}
if(count+1==S.size()){
Set result=new Set{};
for(Element a:S){
result+=new Set{S-{a}};//集合依次排除一個元素產(chǎn)生的子集作為結(jié)果的一個元素
}
return result;
}
Set S2=combine(count-1,S-S(0));//對應(yīng)YH公式的后一項,S(0)為集合S的第一個元素
for(Set Si:S2){
Si+={S(0)};//Si是缺了一個元素的
}
Set S1=combine(count,S-S(0));//這個是個數(shù)整好的,YH公式的前一項
return S1+S2;//YH公式
}
這個問題比較有意思,不知道誰出的.沒有中學(xué)組合知識或YH公式,真困難了.
要是誰有更好算法,不妨交流一下.
這題分給的夠低了,純屬興趣做一下玩.