题目描述

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

输入格式
输入一个整数n。

输出格式
每行输出一种方案。

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

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

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

样例

输入样例：
3
输出样例：

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

算法1

(dfs + 位运算) $O(n^2)$

C++ 代码

#include <iostream>
using namespace std;
int n;
bool vis[17];
int a[17];

void dfs(int u,int state) //枚举第u + 1 的选与不选
{
    if(u == n)
    {
        for(int i = 0 ; i < 16 ; i++)
            if((state >> i)&1)
                cout<< ( i + 1 )<<" ";

            cout<<endl;

        return ;
    }

    dfs(u + 1 , state); //先枚举不选，由题目样例可得第一个数字大的选法先输出
    dfs(u + 1 , state|(1 << u));//枚举选，因为 u 是递增的，
                                //所以state中的要变成一的那位数也是向高位选择
                                //如state = 0000001 （选取了第一位）
                                //如果此时u为2，那么 
                                //state | (1 << u) = 0000001 | 0000101，即选择了 1 3
}

int main(){
    cin>>n;

    dfs(0,0)；


    return 0;
}

算法2

(暴力枚举) $O(n^2)$

C++ 代码

#include <iostream>
using namespace std;
int n;

int a[17];

void dfs(int u) 
{
    if(u == n)
    {
        for(int i = 0 ; i < n ; i ++)
            if(a[i] == 1)
                cout<< i + 1 <<" ";

    cout<<endl;

    return;
    }

    a[u] = 2;
    dfs(u + 1);
    a[u] = 0;

    a[u] = 1;
    dfs(u + 1);
    a[u] = 0;

}

int main(){
    cin>>n;

    dfs(0);


    return 0;
}