递归实现指数型枚举

递归实现指数型枚举

1、题目内容

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

2、输入格式

输入一个整数 n。

3、输出格式

每行输出一种方案。

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

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

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

4、数据范围

1≤n≤15

5、输入样例

3

6、输出样例

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

7、分析

二叉搜索树思想

每个数被选取的状态可以采用数组或者位运算来进行记录

解题思路：从前往后依次枚举每个数，每个数选与不选分别会走在两个分支里去，最终二叉搜索树（递归搜索树）的叶子节点就是最终的方案，中间节点都有两个选择即选与不选。

8、代码实现

#include<iostream>
using namespace std;

int n;

void dfs(int u,int state){
     //记录状态可以用数组来记录，也可以使用位运算来记录，此题采用位运算来记录
    if(u == n){
        for(int i=0; i<n; i++)
            if(state>>i & 1)  //判断state的第i位是否为1
                //注：怎么判断state的第i位是否为1，就把state右移i位再与1
                cout<<i+1<<' ';
        cout<<endl;
        return;
    }

    dfs(u+1, state);  //该数不用
    dfs(u+1, state | 1<<u);  //把state的第u个位置成1
}

int main(){

    cin>>n;
    dfs(0,0);
    return 0;
}

9、递归思想

递归 思想 —— 从后往前算，就是把当前问题划归成几个简单的子问题，然后分别处理完每个子问题，最后再将子问题的解进行整合。