递归解决n个整数中指数级选择方案的C++代码

递归实现指数型枚举是一种算法问题，主要涉及组合数学和深度优先搜索（DFS）的概念。该问题要求在给定整数范围内，从1到n（包含1和n）的所有整数中，找出所有可能的子集选择，并按照特定格式输出。题目中的关键点在于如何利用递归方法生成所有可能的选择，并且保证输出的每个方案都是有序的，相邻数之间只间隔一个空格。 题目中的核心函数`dfs`（深度优先搜索）是递归的核心部分。它接受两个参数：`u`表示当前正在枚举的数，而`state`是一个二进制数，通过位运算来记录当前选择的数字。函数的逻辑可以分为两个分支： 1. 当`u`等于`n`时，这意味着已经枚举到了所有可能的数，此时需要输出当前的`state`所对应的子集。遍历二进制`state`，如果第`i`位（从0开始计数）为1，则表示第`i`个数被选中，将其输出并加上前导的空格，最后换行。 2. 对于`u`不等于`n`的情况，递归地进行两种操作： - `dfs(u+1, state)`：跳过当前数`u`，即不选择它，继续枚举下一个数。 - `dfs(u+1, state | (1 << u))`：选择当前数`u`，通过位或运算`state | (1 << u)`更新状态，将`u`的二进制表示的1（左移一位）与`state`合并，表示`u`已被选中。 `main`函数首先读取输入的整数`n`，然后调用`dfs`函数开始递归，初始参数为`0`和`0`（表示初始时没有选择任何数）。递归会一直持续到`u`达到`n`为止，输出所有可能的子集选择。 这个问题的难点在于如何使用二进制位运算有效地表示和跟踪选择状态，以及如何利用递归来遍历所有组合。这种算法的时间复杂度是O(2^n)，因为它会生成所有可能的子集，而空间复杂度是O(n)，因为递归栈最多会保存到n层。需要注意的是，由于题目允许行间顺序任意，所以在实际输出时无需担心相邻方案的顺序问题。