递归实现指数型枚举

题目描述

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

输入格式

输入一个整数n。

输出格式

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

1\(\leq\)n \(\leq\) 15

输入样例

3

输出样例

3
2
2 3
1
1 3
1 2
1 2 3

算法1

1~n这n个数字每个数字都有输出与不输出两种选择。所以所有的输出方案共有\(2^n\)种。
我们可以考虑使用状态压缩的非递归做法。
状态压缩的特性：可以枚举所有选与不选的情况。
可以用state的二进制表示形式中每位上的0/1体现每个数字的‘不选/选‘。
eg：
当n=3时，共有8中输出方案。
state=0 ——> 000 ——>一个数字也不输出
state=1 ——> 001 ——>输出数字1
state=2 ——> 010 ——>输出数字2
state=3 ——> 011 ——>输出数字1 2
state=4 ——> 100 ——>输出数字3
state=5 ——> 101 ——>输出数字1 3
state=6 ——> 110 ——>输出数字2 3
state=7 ——> 111 ——>输出数字1 2 3

C++ 代码

#include<iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int state=0;state<(1<<n);state++)
    {
        for(int j=0;j<n;j++)
        {
            if(state>>j&1)
            cout<<j+1<<" ";
        }
        cout<<endl;
    }
    return 0;
}

算法2

(非递归暴力枚举) \(O(n^2)\)

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

递归实现指数型枚举

原文：https://www.cnblogs.com/Acapplella/p/13548547.html