一道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) 　　既然有了公式,递归就很好实现了 　　INTC(N,K){ 　　if(K==1)returnN; 　　else 　　renturnC(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%也解决了.这题也就完成咯

　　首先非常感谢您的详细解答，大部分我看懂了，可还是有点云里雾里，您能不能把代码写下，我比较笨，一搬看别人题解的时候，我都要结合代码理解，一点一点拿数据模拟代码执行过程，能帮忙写下吗？具体代码不知道咋写QAQ

　　这里注意，如果题目没有限定K的大小，即一个集合可能会有无限个数，所以用来记录集合的数组S就需要是动态的，需要在main()中初始化 　　//全局变量 　　int N; 　　int K; 　　int S[20]; 　　void Fun(int N1,int K1){ 　　int A=K-K1,B=N-N1,C=B+1,D=N,E=K1;//其实C、E只有在K1==1的时候有用，D一直都是等于N，所以也是没有用的， 　　S[A] = B; 　　if(K1==1){//当K1==1的时候，直接就可以输出了，不用递归 　　for(int i=C;i<=N;i++){ 　　S[K] = i; 　　print(); 　　} 　　} 　　else{//当K1>=2的时候才需要递归 　　for(int i=1;N1-i>=K1-1;i++){ 　　Fun(N1-i,K1-1); 　　} 　　} 　　} 　　void print(){//打印集合，输出数组S[1]到S[K]的具体数 　　for(int i=1;i<=K;i++){ 　　cout<<S[i]<<" "; 　　} 　　cout<<"n"; 　　} 　　int main(){ 　　输入N和K; 　　C(N,K); 　　} 　　C++很久没用，具体语法不知道对不对