一道ACM组合水题

Question

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

比如输入5 3
输出为
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
.....
3 4 5
求思路，如果有代码更好

Answer 1

代码就不贴了，给你思路吧
这个题其实就是求集合数的具体集合。

如果不是输出具体集合，而是输出具体有多少个集合，那么这题很简单。
以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,1)什么意思？与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++很久没用，具体语法不知道对不对