AcWing 92.递归实现指数型枚举（详解）

[dfs入门必看]

题目概述

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

输入格式

输入一个整数 n。

输出格式

每行输出一种方案。同一行内的数必须升序排列，相邻两个数用恰好 1个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

1≤ n ≤15

输入样例:

3

输出样例：

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

• 本题相当于是dfs模型题，重点掌握其思想
• 分析题目
  • 从n个数中任意选择任意个，显然用寻常的循环很难解决，上一个数选不选对这个数并无影响，但对结果是有影响的。此时，我们可以考虑用递归来解决
    下图就是一颗递归搜索树，也是解决问题的关键
    • 用 n = 3 举例说明。我们依次判断这3个位置，每个位置上的数数就两种情况，选还是不选，由此我们就画出了类似树的结构
      
  • 怎样将这个图转化为代码？

1. 我们先创建一个状态数组

   const int N = 16;
   int n; 
   int st[N]; // 记录每一位的状态，0表示没考虑，1表示选，2表示不选
   

2.然后对每一位进行判断

//参数表示当前该考虑哪一位  从第一位开始
void dfs(int u) {
	// 临界
	if (u > n) {
		// 看哪个位置是被选中的，然后输出
		for (int i = 1; i <= n; i ++) {
			if (st[i] == 1)
				printf("%d ",i);// 注意数后的空格
		}
		cout << endl;
		return;
	}
	// 第一个分支，不选
	st[u] = 2;
	dfs(u + 1);// 计算下一个位置
	st[u] = 0;// 回溯，当前分支计算完后，要将状态恢复
	
	// 第二个分支，选
	st[u] = 1;
	dfs(u + 1);
	st[u] = 0;
}

• 完整代码

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 16;
int n; 
int st[N]; // 记录每一位的状态，0表示没考虑，1表示选，2表示不选

//参数表示当前该考虑哪一位  从第一位开始
void dfs(int u) {
	// 临界
	if (u > n) {
		for (int i = 1; i <= n; i ++) {
			if (st[i] == 1)
				printf("%d ",i);
		}
		cout << endl;
		return;
	}

	st[u] = 2;
	dfs(u + 1);
	st[u] = 0;

	st[u] = 1;
	dfs(u + 1);
	st[u] = 0;
}

int main() {
	cin >> n;
	dfs(1);
	return 0;
}

• 本题结束，图和思想是重点，理清后，代码写一遍就会了
  对本题还有疑问的话可以打在评论区，别忘了点赞和收藏！