一道ACM组合水题给出一个正整数N,从集合{1,2,3..N},中找出所有大小为k的子集,并且按照字典序由小到大输出,n,k

一道ACM组合水题给出一个正整数N,从集合{1,2,3..N},中找出所有大小为k的子集,并且按照字典序由小到大输出,n,k
一道ACM组合水题
给出一个正整数N,从集合{1,2,3..N},中找出所有大小为k的子集,并且按照字典序由小到大输出,n,k

一道ACM组合水题给出一个正整数N,从集合{1,2,3..N},中找出所有大小为k的子集,并且按照字典序由小到大输出,n,k
代码就不贴了,给你思路吧
这个题其实就是求集合数的具体集合.
如果不是输出具体集合,而是输出具体有多少个集合,那么这题很简单.
以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%也解决了.这题也就完成咯