使用递归求出一个集合的所有子集

淩亂°似流年 2022-09-26 11:54 165阅读 0赞

想一下，平时如果给你1，2，3，4四个数，让你写出它的所有子集，你会怎么做？  
我想大部分人的思路是先写出子集中只含有一个元素的子集:1;2;3;4。然后考虑子集中含有两个元素的子集:1,2;1,3;1,4;2,3;2,4;3,4。然后是子集中含有三个元素的子集:1,2,3;1,2,4;1,3,4;2,3,4。最后是自己:1,2,3,4。当然别忘了还有一个空集。  
好的，如果能够这么想说明思路还是挺清晰的。我们现在写的程序的思路和这个是一样的:先用循环控制每次找的子集的元素个数，然后在函数中开始复原刚才我们手写时的思路。在开始实验之前我们先要了解一个技巧:比如我们想输出abcd中的acd，那么我们可以用1011来表示，然后最终输出的时候判断每个字符对应的是1还是0。  
比如我们要查找\{a,b,c,d,e\}这个集合的含有三个元素的子集。我们查找时先固定a(也就是a对应的是1),然后我们接下来的目标是从剩下的\{b,c,d,e\}中找出两个，显然这项工作和我们之前的是一样的，所以可以调用递归函数来解决这个问题。现在我们先不管这个递归函数具体怎么写，先整清楚思路。假如现在已经完成了含有a的子集，那么再来固定b(也就是b对应的是1)，这时候别忘了将a对应的1改成0，否则到时候又要把a输出了。现在我们要清楚接下来得从\{c,d,e\}中找出两个数。完成了b，再对c,d,e做同样的工作。等等！貌似如果要找出含有3个元素的子集的话，只需要分别对a,b,c固定就行了吧，如果是d或者e根本就凑不出三个吧。嗯，所以我们只需要对a,b,c固定即可。  
现在我们大概搞清楚了该怎么写这个递归函数，还有一个疑惑就是这个递归函数究竟什么时候结束呢?我们想想，对这个函数递归到最后还剩几个元素呢？答案是1个！所以当我们要在剩余没有固定住的元素中找到一个的话就不需要再调用递归函数了，而是直接用for循环在剩余的数中依次取出来利用刚才的01方法决定输出abcde中的哪几个。完整的思路就是这样的。  
现在我们来将上面的思路用代码的形式写出来:

//关于为什么大小设成27:因为这样方便，要是老去考虑下标加1减1之类的太麻烦
    //a:bitset<27>类型的变量，用来保存1和0. chr:存有a->z的大小为27的char数组 
    void CSet(int index, int n,int size) {
       //index:当前下标 n:我们要在剩下的数中取出n个 size:共有size个元素
        if (n == 0)//空集
            cout << endl;
        else if (n == 1) {
       //要在剩下数种取出1个
            for (int i = index; i <= size; i++) {
                a[i] = 1;
                for (int i = 1; i <= size; i++)
                    if (a[i])
                        cout << chr[i]<<" ";
                cout << endl;
                a[i] = 0;
            }
        }
        else {
       //当要在剩下数中取出2个及以上时用递归
            for (int i = index; i <= size - n+1; i++) {
                a[i] = 1;
                CSet(i + 1, n - 1, size);
                a[i] = 0;
            }
        }
    }

现在假如我们要找出26个字母组成的集合的所有子集，就可以这样写:

for (int i = 0; i <= 26; i++) {
            cout << "下面是集合中元素为" << i << "个的集合:" << endl;
            CSet(1, i, n);
        }

介绍完上面看上去较为繁琐的方法，现在来介绍另一个奇技淫巧:  
不知你是否看出上面的本质就是输出从00000000000000000000000000（别数了，26个0）到 11111111111111111111111111，所以我们另一种方法是把一个二进制数从0一直加到2^26-1，每次只加1然后输出即可。这里就不贴代码了。