Subsets (Power Set)

Bit ManipulationArrayBacktracking

20 min

Problem Statement

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

Example

Example 1:

Input: nums = [1,2,3]

Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Solution (Bitmasking)

While this problem is a classic for recursion and backtracking, it has a particularly elegant solution using bit manipulation. For a set of n elements, there are 2^n subsets. We can map each integer from 0 to 2^n - 1 to a unique subset.

Each integer acts as a "bitmask," where the j-th bit of the integer corresponds to the j-th element of the input array. If the bit is 1, the element is included in the subset; if it's 0, it's excluded.

Algorithm Steps

Let n be the number of elements in nums.
The total number of subsets will be 2^n.
Iterate from i = 0 to 2^n - 1. Each i is a bitmask.
For each i, create a new subset.
Iterate from j = 0 to n - 1.
If the j-th bit of i is set (i.e., (i >> j) & 1 is 1), add nums[j] to the current subset.
Add the newly created subset to the list of all subsets.

Input `nums`:

Mask (i): N/A

Checking Bit (j): N/A

Current Subset: []

Generated Subsets:

Initializing. Total subsets to generate: 2^3 = 8.

Subsets (Power Set) Solution


from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        output = []
        
        for i in range(1 << n):
            subset = []
            for j in range(n):
                if (i >> j) & 1:
                    subset.append(nums[j])
            output.append(subset)
            
        return output