栈实现指数型枚举

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

题目描述

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

输入描述:

一个整数n。

输出描述:

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

示例1

输入

3

输出

3

2
2 3
1
1 3
1 2
1 2 3

利用栈与队列的特点与数的顺序进行枚举

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
stack<ll>sum1;
queue<ll>sum2;
void process(int num)
{
    for (int i = 1; i <= num; i++)
        sum1.push(i);//升序入栈
    while (!sum1.empty())
    {
        ll temp1 = sum1.top();
        sum1.pop();//出栈
        bool f = 1;
        for(int i=0;i<sum2.size();i++)//检验是否可以升序插入，如果不可以将第一个比当前出栈的数大的前面所有数放到后面
        if (sum2.front()<temp1)
        {
            sum2.push(sum2.front());
            sum2.pop();
        }
        else
        {
            f = 0;
            break;
        }
        if (sum2.empty() || f)//如果可添加到队列
        {
            sum2.push(temp1);
            queue<ll>temp2;
            while (!sum2.empty())
            {
                temp2.push(sum2.front());
                sum2.pop();
            }
            while (!temp2.empty())
            {
                sum2.push(temp2.front());
                cout << temp2.front() << ' ';
                temp2.pop();
            }
            cout << endl;
        }
        else {//如果不可添加到队列，则入栈

            sum1.push(sum2.front());
            sum1.push(temp1);
            sum2.pop();
        }
    }
}
int main()
{
    int n;
    cin >> n;
    process(n);
    cout << endl;//打印什么都不选的情况
    return 0;
}