Subsets

How it works

Start with just one subset: the empty set [].

For every number in the array, we take all the subsets we have so far and create new subsets by adding the current number to each of them.

Example:

• Start: [[]]
• Add 1 → [[], [1]]
• Add 2 → [[], [1], [2], [1,2]]
• Add 3 → [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

Each step doubles the number of subsets.

Steps

1. Initialize res = [[]] (start with empty subset).
2. For each number num in the input array:
   • For every subset already in res:
     • Create a new subset that includes num
   • Append all these newly created subsets to res.
3. Return res after processing all numbers.

Complexity

• Time complexity: O(n * 2 ^ n)
• Space complexity:
  • O(n) extra space.
  • O(2 ^ n) for the output list.

Things to watch for

Modifying the Subset After Adding to Result

When adding a subset to the result list, you must add a copy of the current subset. Otherwise, backtracking modifications will alter subsets already in the result.

Forgetting the Empty Subset

The power set always includes the empty subset []. Forgetting to initialize with an empty subset or starting the iteration incorrectly will miss this case.

Incorrect Index Handling in Backtracking

When recursing, start from i + 1 to avoid reusing the same element and to prevent duplicate subsets. Starting from 0 or i generates incorrect results.

Integer Overflow in Bitmask Approach

For the bitmask solution, 1 << n can overflow for large n. In most languages, this limits the approach to around 30 elements, though problem constraints usually keep n small.

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]

        for num in nums:
            res += [subset + [num] for subset in res]

        return res

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res = {{}};

        for (int num : nums) {
            int size = res.size();
            for (int i = 0; i < size; i++) {
                vector<int> subset = res[i];
                subset.push_back(num);
                res.push_back(subset);
            }
        }

        return res;
    }
};