数据结构作业：求幂集

Code

#define REP(x, y) for (int i = (x); i <= (y); ++i)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 2;

int n;
int s[N], PowTable[N] = {1};

void subset(int s[], int order) {
    if (order == 0) {
        cout << "{}\n";
        return;
    }

    subset(s, order - 1);

    cout << "{";

    int table[N] = {0};
    int lastPos;

    REP(1, n) {
        table[i] = order & 1;
        lastPos = table[i] ? i : lastPos;
        order = order >> 1;
    }

    REP(1, lastPos - 1) {
        if (table[i]){
            cout << s[i] << ", ";
        }
    }
    cout << s[lastPos];

    cout << "}\n";
}

int main(int argc, char const* argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    REP(1, n) cin >> s[i];

    REP(1, n) PowTable[i] = PowTable[i - 1] << 1;

    subset(s, PowTable[n] - 1);
    return 0;
}

Review

有手就行。

Recursion 是因为要求 recursion，所以套了一个。

本质上是取或不取构成的二进制串和生成的子集一一对应，所以可以直接数出来。

Like，对于{1, 2, 3}而言，1，也就是二进制001，也就是{0, 0, 1}，对应{3}这个子集。

当然为了可读性，修改了代码里输出的顺序，也加入了最后元素输出坐标的检查。

Example Input

5
1 2 3 4 5

Example Output

{}
{1}
{2}
{1, 2}
{3}
{1, 3}
{2, 3}
{1, 2, 3}
{4}
{1, 4}
{2, 4}
{1, 2, 4}
{3, 4}
{1, 3, 4}
{2, 3, 4}
{1, 2, 3, 4}
{5}
{1, 5}
{2, 5}
{1, 2, 5}
{3, 5}
{1, 3, 5}
{2, 3, 5}
{1, 2, 3, 5}
{4, 5}
{1, 4, 5}
{2, 4, 5}
{1, 2, 4, 5}
{3, 4, 5}
{1, 3, 4, 5}
{2, 3, 4, 5}
{1, 2, 3, 4, 5}