LeetCode Hot 100 P78 Subsets

---

Timeline

timeline

2026-03-16

init

backtracking

---

Problem:

P78 Subsets

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

What first came to my mind was formulaic backtracking:

#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 all elements in distinct
                 */
                vector<vector<int> > subsets;
                vector<int> curr;
                unordered_set<int> uset;
                int i, n = nums.size();

                subsets.push_back({}); // empty set

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

                subsets.push_back(nums); // full set
                return subsets;
        }
};

The LeetCode solution recommends using bit manipulation, which is indeed very clever

0/1 sequence	subsets	binary number corresponding to a 0/1 sequence
000	{}	0
001		1
010		2
011		3
100		4
101		5
110		6
111		7

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;
    }
};