《算法竞赛进阶指南》递归实现指数型枚举--题解

题目描述
从 1\sim n1∼n这 n (n \leq 16)(n≤16) 个整数中随机选取任意多个，输出所有可能的选择方案。

输入描述:
一个整数n。

输出描述:
每行一种方案。同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。对于没有选任何数的方案，输出空行。本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

这道题有多种解法，这里只介绍状态压缩版：

状态压缩的特性：
可以枚举所有选与不选的情况。

实例：
不难发现题目输出的结果都为2^n：
当n为2时输出：
000->/n
001->1
010->2
011->1 2
当n为3时输出：
000->/n
001->1
010->2
100->3
011->1 2
101->1 3
110->2 3
111->1 2 3

C++状压递归版：

#include <iostream>

using namespace std;

int N;

void dfs(int n, int state)//n为当前枚举到的数,state是记录哪些数被选
{
    if (N == n) {
        for (int i = 0; i < n; i++)
            if (state >> i & 1) 
                cout << i + 1 << " ";
            cout << endl;
        return;
    }
    dfs(n + 1, state);//不用n这个数
    dfs(n + 1, state | (1 << n));//用n这个数
}
int main() {
    cin >> N;
    dfs(0, 0);
}

虽然题目是递归，但我从小就不是一个唯命是从的人
所以
C++状压非递归版：

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    //state表示每一种状态
    for (int state = 0; state < (1 << n); state++)
    {
        //用i遍历整个state并输出
        for (int i = 0; i < n; i++)
            if (state >> i & 1)
                cout << i + 1 << " ";
        cout << endl;
    }
    return 0;
}

我觉得每到题不一定只有一种答案呢，以上只给出两种还有例如vector枚举来解的等等......