递归实现指数型枚举

// 递归实现指数型枚举
#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;
}