题意概括

给定一个不包含重复元素的整数数组 nums，你的任务是找出该数组所有可能的子集（也称为幂集）。

输出要求:

• 返回的解集中不能包含重复的子集。
• 你可以按照任意顺序输出所有子集。
• 每个子集占一行，元素间用空格分隔。如果子集为空（即空集），则输出一个空行。

数据范围:

• 数组长度 n 通常在 $1 \le n \le 20$ 的范围内，因为子集的数量会以 $2^n$ 的速度爆炸式增长。

基础知识

求解一个集合的所有子集是组合问题中的一个基本模型。解决这类问题最常用且最重要的方法之一就是 回溯法 (Backtracking)，它本质上是一种带有“剪枝”的深度优先搜索 (DFS)。

回溯法 (Backtracking / DFS) 思想:

我们可以把寻找所有子集的过程，想象成构建一棵“决策树”。对于原数组中的每一个元素，我们都面临一个决策：是将这个元素加入到当前正在构建的子集中，还是不加入。通过系统性地遍历这棵决策树的所有路径，我们就能找到所有可能的子集。

算法流程:

我们通常会设计一个递归函数，例如 dfs(int startIndex, vector<int>& currentPath)，来执行这个搜索过程。

1. 函数参数:

   • startIndex: 这个参数至关重要，它指定了我们下一次选择元素的起始位置。例如，当我们已经选择了 nums[0] 后，下一次的选择就应该从 nums[1] 开始，而不能再回头选择 nums[0]，这样可以避免生成重复的组合。
   • currentPath: 这个参数（通常是一个列表或向量）记录了从根节点到当前节点所做的一系列选择，即当前已经构建出的子集。

2. 递归过程:

   • 收集结果: 每当递归函数被调用时，currentPath 本身就代表一个有效的子集（包括第一次调用时的空集）。因此，在函数的一开始，我们就应该将 currentPath 的一个副本添加到最终的结果集 res 中。
   • 遍历与决策: 从 startIndex 开始，向后遍历数组中的所有元素。 a. 做出选择 (Choose): 将当前遍历到的元素 nums[i] 添加到 currentPath 的末尾。 b. 向下探索 (Explore): 以 i + 1 作为新的 startIndex 递归调用 dfs 函数，去构建更长的子集。 c. 撤销选择 (Unchoose / Backtrack): 当从深层递归调用返回后，必须将刚才添加的元素 nums[i] 从 currentPath 中移除。这一步是“回溯”的精髓所在，它意味着我们撤销了当前的选择，返回到上一个状态，以便去尝试其他的选择分支（比如，在探索了包含 nums[i] 的所有子集后，我们现在要去探索不包含 nums[i] 的其他可能性）。

3. 初始调用: 在主逻辑中，我们从 dfs(0, emptyPath) 开始，表示从数组的第一个元素开始，基于一个空集进行构建。

复杂度分析:

• 时间复杂度: 共有 $2^N$ 个子集。为构造每个子集，需要将其元素添加到一个临时列表中，平均长度为 $N/2$。因此，总的时间复杂度为 $O(N \times 2^N)$。
• 空间复杂度: 存储所有子集需要 $O(N \times 2^N)$ 的空间。递归调用栈的深度最多为 $N$，所以还需要 $O(N)$ 的栈空间。

C++ 解决方案

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n;
vector<int> v;
vector<vector<int>> res;
vector<int> path;

// 回溯函数
// idx: 当前选择的起始索引
void dfs(int idx) {
    // 1. 将当前路径作为一个子集加入结果集
    res.push_back(path);

    // 2. 从 idx 开始遍历，做出选择
    for (int i = idx; i < n; ++i) {
        // a. 做出选择
        path.push_back(v[i]);
        
        // b. 向下探索
        dfs(i + 1);
        
        // c. 撤销选择 (回溯)
        path.pop_back();
    }
}

void slv() {
    cin >> n;
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }

    dfs(0);

    // 输出所有子集
    for (const auto& subset : res) {
        if (subset.empty()) {
            cout << endl; // 空集输出空行
        } else {
            for (int i = 0; i < subset.size(); ++i) {
                cout << subset[i] << (i == subset.size() - 1 ? "" : " ");
            }
            cout << endl;
        }
    }
}

int main() {
    // 关闭同步流，加速IO
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    slv();

    return 0;
}

/*
样例输入 1:
3
1 2 3

样例输出 1:
(顺序可能不同，但内容一致)

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

样例输入 2:
1
0

样例输出 2:

0 
*/