时间轴

2026-03-16

init

题目：

P78 子集

https://leetcode.cn/problems/subsets/description/?envType=study-plan-v2&envId=top-100-liked

我最开始想到的就是公式化回溯：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <vector>
#include <unordered_set>

using std::vector;
using std::unordered_set;

class Solution {
    private:
        void __subsets(vector<int> &nums, vector<vector<int> > &subsets, vector<int> &curr,
                       unordered_set<int> uset, int nr, int start)
        {
                if (curr.size() == nr) {
                        subsets.push_back(curr);
                        return;
                }

                int i, n = nums.size();
                for (i = start; i < n; i++) {
                        if (uset.count(nums[i]))
                                continue;

                        curr.push_back(nums[i]);
                        uset.insert(nums[i]);

                        __subsets(nums, subsets, curr, uset, nr, i + 1);

                        curr.pop_back();
                        uset.erase(nums[i]);
                }
        }

    public:
        vector<vector<int> > subsets(vector<int> &nums)
        {
                /*
                 * 1 <= nums.length <= 10
                 * -10 <= nums[i] <= 10
                 * nums 中的所有元素 互不相同
                 */
                vector<vector<int> > subsets;
                vector<int> curr;
                unordered_set<int> uset;
                int i, n = nums.size();

                subsets.push_back({}); // 空集

                for (i = 1; i < n; i++)
                        __subsets(nums, subsets, curr, uset, i, 0);

                subsets.push_back(nums); // 满集
                return subsets;
        }
};

leetcode 题解中方法推荐利用位运算，确实很巧妙

0/1 序列 子集 0/1 序列对应的二进制数
000 {} 0
001 {9} 1
010 {2} 2
011 {2, 9} 3
100 {5} 4
101 {5, 9} 5
110 {5, 2} 6
111 {5, 2, 9} 7 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> t;
    vector<vector<int>> ans;

    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if (mask & (1 << i)) {
                    t.push_back(nums[i]);
                }
            }
            ans.push_back(t);
        }
        return ans;
    }
};