递归实现指数型枚举

2023-12-31 16:36:22
// 递归实现指数型枚举
#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)// 看第i位选没选
			{
				cout << i + 1 << " ";// 二进制从第零位开始,所以输出要加一
			}
		}
		cout << "\n";
		return;
	}

	// 为什么不选当前数不需要做额外操作?
	// 因为state初始是从0开始的,从低位往高位枚举,
	// 当枚举到第n为的时候,state的第n为本来就是0
	dfs(u + 1, state);// 不选当前的数
	// << 优先级比 | 高,所以提前把第u位置为1,这样就保证state的第u位为1
	dfs(u + 1, state | 1 << u);// 选第u个数,将第u位的数置为1
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	dfs(0, 0);
	return 0;
}

文章来源:https://blog.csdn.net/qq_73185160/article/details/135316993
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。