92. 递归实现指数型枚举

理解题目

给出一个数字n，输出1~n中任意取出1个或者多个的情况，数字的顺序必须是从小到大。

解题思路

依次递归每一个位置，有选和不选两种情况，使用一个visit[N]数组去记录这个元素是否输出，当遍历到最后一个为止的时候，输出所有被visit数组标记为true的元素。

• c++代码

#include<iostream>
using namespace std;
const int N = 20;
int n;
bool vist[N];// 判断是选还是不选
void dfs(int u){
    if(u > n){
        for(int i = 1; i <= n; i ++){
            if(vist[i]){// 这个位置放置了数字i
                cout << i << " ";
            }
        }
        cout << endl;
    }else{
        vist[u] = true;
        dfs(u + 1);// 选择u这个数字之后进入下一层递归
        vist[u] = false;
        dfs(u + 1);// 不选择u这个数字之后进入下一层递归
    }
}
int main(){
    cin >> n;
    dfs(1);
    return 0;
}

• java代码