题目描述

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

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

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

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

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

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

数据范围
1≤n≤15

样例

输入样例：
3
输出样例：

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

算法1

(递归)

1~n中每一个数都有两种状态：选择与不选
将1~n看成递归的层数dfs(u)，那么每层可以有两种选择：u是否需要

C++ 核心代码

void dfs(int u){
    if(u>n){
        for(int i=1;i<=n;i++)
            if(a[i])
                cout<<a[i]<<" ";
        puts("");
        return ;
    }
    dfs(u+1);//不输出u

    a[u]=u;//输出u
    dfs(u+1);
    a[u]=0;//注意选择了之后需要及时更新
}

算法2

(压位) $O(2^n)$

可以用二进制的0 1来代表对应数字是否选择

C++ 核心代码

void wei(){
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            if(i>>j&1)
                cout<<(j+1)<<" ";
        }
        puts("");
    }
}

AC代码

#include<iostream>
using namespace std;
const int N=16;
int n;
int a[N];
void wei(){
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            if(i>>j&1)
                cout<<(j+1)<<" ";
        }
        puts("");
    }
}
void dfs(int u){
    if(u>n){
        for(int i=1;i<=n;i++)
            if(a[i])
                cout<<a[i]<<" ";
        puts("");
        return ;
    }
    dfs(u+1);
    a[u]=u;
    dfs(u+1);
    a[u]=0;
}
int main(){
    cin>>n;
    //dfs(1);
    wei();
    return 0;
}