第一讲 递推与递归

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]){// 这个位置放置了数字icout << 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代码