组合数的输出

https://www.luogu.com.cn/problem/P1157

以$n=5$为例，那么原集合就是{$1,2,3,4,5$}
按照每个数字是否存在于子集合中可能有:
{$0,0,0,0,0$} ---->{}
{$0,0,0,0,1$} ---->{$5$}
{$0,0,0,1,0$} ---->{$4$}
{$0,0,0,1,1$} ---->{$4,5$}
{$0,0,1,0,0$} ---->{$3$}
…

这样的二进制形式，就可以模拟出所有的子集选择情况。

这些二进制，还是可以从0，一直到 31的， 也就是说，我们可以用循环从0遍历到31，就成功模拟了这32种情况，对应着32种子集合。假设我们写出了如下的代码：

for(int i=0;i<31;i++){
    ...
}

由于数字是从$0$到$31$，所以第一个考查的是0，第二个考查的是1，最后一个考查的是31,对应二进制就是：

由于例子是$r=3$,所以：

#include <bits/stdc++.h>

using namespace std;
const int N = 30;
int a[N];

int main() {
    int n, r;
    cin >> n >> r;

    //如果是正序
    for (int S = 0; S <= (1 << n) - 1; S++) {
        //每次循环需要清0
        memset(a, 0, sizeof a);
        int cnt = 0;

        for (int i = n - 1; i >= 0; i--)    //遍历S的每一个二进制位(从高位到低位)
            if (S & (1 << i)) a[cnt++] = i; //记录S的哪些数位不为0

        //只需要r位
        if (r == cnt) {
            cout << S << "    {";
            /*
             数组内容4，对应着数字1
             数组内容3，对应着数字2
             数组内容2，对应着数字3
             数组内容1，对应着数字4
             数组内容0，对应着数字5
             就是一个两者相加等于n的关系。
             */
            for (int i = 0; i < cnt; i++) cout << n - a[i] << " ";
            cout << "}\n";
        }
    }
    return 0;
}

大数在前，才能保证 10110 早于 10101.修改一下：

#include <bits/stdc++.h>

using namespace std;
const int N = 30;
int a[N];

int main() {
    int n, r;
    cin >> n >> r;

    //大数在前，才能保证 10110 早于 10101
    for (int S = (1 << n) - 1; S >= 0; S--) {
        //每次循环需要清0
        memset(a, 0, sizeof a);
        int cnt = 0;

        for (int i = n - 1; i >= 0; i--)    //遍历S的每一个二进制位(从高位到低位)
            if (S & (1 << i)) a[cnt++] = i; //记录S的哪些数位不为0

        //只需要r位
        if (r == cnt) {
            printf("%3d", S);
            cout << "    { ";
            /*
             数组内容4，对应着数字1
             数组内容3，对应着数字2
             数组内容2，对应着数字3
             数组内容1，对应着数字4
             数组内容0，对应着数字5
             就是一个两者相加等于n的关系。
             */
            for (int i = 0; i < cnt; i++) cout << n - a[i] << " ";
            cout << "}\n";
        }
    }
    return 0;
}