LeetCode56 - 子集 | 很多时候不懂事

📝 题目描述

题目链接：子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

数组的子集是从数组中选择一些元素（可能为空）。

示例：

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素互不相同

💡 解题思路

方法一：递归

套用“全排列”的模板写法即可，不过这里由于 start 变量的存在，我们只能选择 start 之后的数字，避免了重复，因此可以舍弃 used 数组。

步骤：

首先用一个 track 来记录当前已经选好的数字序列。
子集长度从 0 到 n，用一个循环来遍历。
在每一层递归中，如果 track 长度达标则加入 ans 数组，否则从头到尾遍历整个 nums 数组。
从第 start 数开始，将数组的每个数字加入数组，令 start + 1 开始下一次递归。
当递归返回后，把刚才加进去的数字拿出来（track.pop_back()），开始遍历下一个数字。

经过上面的过程，我们就可以得到所有的子集。

方法二：位运算

对于一个长度为 $n$ 的数组，其子集共有 $2n$ 个。我们可以用 $0$ 到 $2^n - 1$ 的整数来表示这些子集。每个整数的二进制表示有 $n$ 位，二进制的第 $i$ 位如果是 $1$ ，就代表 $nums[i]$ 在这个子集中；如果是 $0$ ，则不在。

比如令 nums = [1, 2, 3] $(n=3,2^3=8)$ ：

$0\ \ (000) → [\ \ ]$
$1\ \ (001) → [1]$
$2\ \ (010) → [2]$
$3\ \ (011) → [1, 2]$
$...$
$7\ \ (111) → [1, 2, 3]$

因此，我们可以使用位运算的方式构建每一个子集，将其加入答案数组中。

🔧 代码实现

1、递归

class Solution {
public:
    vector<vector<int>> ans;
    void backtrack(vector<int>& nums, int& total, list<int>& track, int start) {
        // 排好的序列长度 = 规定长度，则加入答案数组并返回
        if (track.size() == total) {
            ans.push_back(vector<int>(track.begin(), track.end()));
            return;
        }

        // 否则从起始位置开始选数入序列
        for (int i = start; i < nums.size(); i++) {
            track.push_back(nums[i]);
            // 递归并更新起始位置
            backtrack(nums, total, track, i + 1);
            track.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        list<int> track;
        // 子集长度从 0 到 n
        for (int i = 0; i <= nums.size(); i++) {
            // 为了避免重复（如 [1,2,3] 和 [2,1,3]），需要指定起始位置
            backtrack(nums, i, track, 0);
        }
        return ans;
    }
};

2、位运算

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        // 获取总数字数量
        int n = nums.size();
        // 获取子集总数，也就是 2 的 n 次方
        int subsetCount = 1 << n;
        vector<vector<int>> ans;

        // 开始构建每一个子集
        for (int mask = 0; mask < subsetCount; mask++) {
            // 创建数组
            vector<int> currentSubset;
            // 开始判断要不要加入数字到数组
            for (int i = 0; i < n; i++) {
                // 判断 mask 的第 i 位是否为 1
                if (mask & (1 << i)) {
                    currentSubset.push_back(nums[i]);
                }
            }
            ans.push_back(currentSubset);
        }
        return ans;
    }
};

📊 复杂度分析

1、递归

时间复杂度： $O(n×2n)$ ，一共 $2n$ 个状态，每种状态需要 $O(n)$ 的时间来构造子集。
空间复杂度： $O(n)$ ，临时列表 track 的空间代价是 $O(n)$ ，递归时栈空间的代价为 $O(n)$ 。

2、位运算

时间复杂度： $O(n×2n)$ ，一共 $2n$ 个状态，每种状态需要 $O(n)$ 的时间来构造子集。
空间复杂度：O(n)。即构造子集使用的临时数组 currentSubset 的空间代价。

🎯 总结

核心思想：掌握回溯法模板。