递归实现指数型枚举

题目

从 1~n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数n。

输出格式

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

输入样例

3

输出样例

思路

递归，二进制状态压缩，顺序枚举

关于递归

递推版

前后关系：f[n] = f[n - 1] + 操作
子问题状态：u
递归结果：无返回值，全局变量vector> num
递归出口：n == 0

并列版

前后关系：从小到大枚举每位数是否被选
子问题状态：u和state(被选情况)
递归结果：无返回值，形参state
递归出口：无剪枝，结束u == n

dfs中非引用型形参，其状态值在当前函数不变。不需要手动回溯。

dfs(u + 1, state | (1 << u)); //选
dfs(u + 1, state); //不选

代码实现

递推版

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> num;

void dfs(int n)
{
    if (n == 0) return;
    dfs(n - 1);

    vector<vector<int>> tmp; //局部变量
    for (auto u : num) //不插入破坏原num 
    {
        auto t = u;
        t.push_back(n);
        tmp.push_back(t);
    }
    for (auto u : tmp) num.push_back(u);
    num.push_back({n});
}

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

    dfs(n);
    for (auto u : num)
    {
        for (auto it : u) cout << it << " ";
        cout << endl;
    }
}

并列版

#include <iostream>
using namespace std;

int n;

void dfs(int u, int state)
{
    if (u == n)
    {
        for (int i = 0; i < n; i++)
        {
            if (state >> i & 1) cout << i + 1 << " "; //state从0开始，数值需要加1
        }
        cout << endl;
        return;
    }
    //两次递归状态相同
    dfs(u + 1, state | (1 << u)); //选
    dfs(u + 1, state); //不选
}

int main()
{
    cin >> n;
    dfs(0, 0); //从0开始顺序枚举，保证升序
}