题目描述

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

输入格式

输入一个整数n。

输出格式

每行输出一种方案。

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

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

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

数据范围

1≤n≤15

输入样例：

3

输出样例：

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

解题思路

递归函数的参数：
1. 当前处理到哪一个数.
2. 当前数选 或 不选.

C ++ 代码

#include <iostream>

using namespace std;

const int N = 20;

bool st[N];
int n;

void dfs(int u){
    if(u > n){//已经递归到叶子节点
        for(int i = 1; i <= n; i ++){
            if(st[i]) cout << i << ' ';
        }
        cout << endl;
        return;
    }

    st[u] = false;//当前数不选
    dfs(u + 1);//处理下一个数

    st[u] = true;//当前数选
    dfs(u + 1);//处理下一个数
    st[u] = false;//恢复现场
}

int main(){
    cin >> n;

    dfs(1);

    return 0 ;
}

C++ 代码1

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 20;

int st[N];//标记当前位状态，即选、不选、未考虑
int n;

void dfs(int u){
    if(u > n){
        for(int i = 1; i <= n; i ++){
            if(st[i] == 1) printf("%d ", i);
        }
        puts("");
        return ;
    }

    st[u] = 2;//当前位不选
    dfs(u + 1);//处理下一位
    st[u] = 0;//恢复现场，可省略

    st[u] = 1;//当前位选
    dfs(u + 1);//处理下一位
    st[u] = 0;//恢复现场，可省略
}

int main(){
    scanf("%d", &n);
    dfs(1);//从第一位开始处理
    return 0;
}

C++ 代码2

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 16;

//ways数组用于记录方案,st数组用于标记当前位置状态，即选、不选、未处理
int ways[1 << 15][16], st[N];
int n, cnt;//cnt用于记录方案数

void dfs(int u){
    if(u > n){
        for(int i = 1; i <= n; i ++){
            if(st[i] == 1) ways[cnt][i] = i;
        }
        cnt ++;
        return ;
    }

    st[u] = 2;//不选当前位
    dfs(u + 1);//从下一位置处理
    st[u] = 0;//恢复现场，可省略

    st[u] = 1;//选当前位
    dfs(u + 1);//从下一位置处理
    st[u] = 0;//恢复现场，可省略
}

int main(){
    scanf("%d", &n);

    dfs(1);

    //输出方案
    for(int i = 1; i <= cnt; i ++){
        for(int j = 1; j <= n; j ++){
            if(ways[i][j]) printf("%d ", ways[i][j]);
        }
        puts("");
    } 

    return 0;
}

C++ 代码3

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 16;

vector<vector<int> > ways;//存储方案
int st[N];//存储当前位置的状态，即选，不选，未考虑
int n;

void dfs(int u){
    if(u > n){
        vector<int> way;//存储每一种方案的具体情况
        for(int i = 1; i <= n; i ++){
            if(st[i] == 1) way.push_back(i);
        }
        ways.push_back(way);
        return ;
    }

    st[u] = 2;//不选当前位置
    dfs(u + 1);//处理下一个位置
    st[u] = 0;//恢复现场，可省略

    st[u] = 1;//选当前位置
    dfs(u + 1);//处理下一个位置
    st[u] = 0;//恢复现场，可省略
}

int main(){
    scanf("%d", &n);

    dfs(1);//从第一个位置开始往后枚举

    for(int i = 0; i < ways.size(); i ++){//输出方案
        for(int j = 0; j < ways[i].size(); j ++){
            printf("%d ", ways[i][j]);
        }
        puts("");
    }

    return 0;
}

C++ 代码4

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

int n;

int main(){
    scanf("%d", &n);

    //将n位数看成是2^n个二进制数，每种情况对应一个二进制数，state表示每个二进制数
    for(int state = 0; state < 1 << n; state ++){
        for(int j = 0; j < n; j ++){
            if(state >> j & 1) printf("%d ", j + 1);
        }
        puts("");
    }

    return 0;
}