Generate all Subsets using Bit Manipulation | Leetcode 78 | Python Code

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Here’s the [Problem Link] to begin with.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

Optimal Approach (Bitwise Masking)

Intuition

Every subset can be represented by a binary number where each bit says “include this element” (1) or “skip it” (0). For an array of size n, there are 2^n possible subsets, matching numbers from 0 to (2^n – 1). For each number, check which bits are set and include those elements in the subset. It’s like using a binary code to unlock all combinations!

Detailed Approach

1. Calculate Total Subsets: There are 2^n subsets, so loop from 0 to (1 << n) – 1.
2. Generate Subset: For each mask (number), check each bit position i.
3. Bit Check: If the i-th bit is set (mask & (1 << i) != 0), include nums[i] in the current subset.
4. Collect Subsets: Build a list for each mask and add it to the result.
5. Return Result: All subsets are generated in a single loop.

Code

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        total_subset = 1 << n  # 2^n subsets
        result = []            # List to store all subsets
        
        # Loop through each possible subset mask
        for num in range(total_subset):
            lst = []           # Current subset
            # Check each bit in the mask
            for i in range(0, n):
                if num & (1 << i) != 0:
                    lst.append(nums[i])  # Include if bit is set
            result.append(lst)   # Add to result
        
        return result

Code Explanation

We calculate the total number of subsets as 2 raised to the power of n (using left shift: 1 << n). Then, for each possible mask from 0 to (2^n – 1), we create a new list. For each bit position i, if the bit is set in the mask (checked with & (1 << i)), we add nums[i] to the list. After checking all bits for that mask, we add the list to our result. This generates all subsets efficiently without recursion.

Time and Space Complexity

• Time Complexity: O(n * 2^n) – For each of 2^n masks, we loop n times to check bits.
• Space Complexity: O(1) – Besides the output, we use constant extra space (ignoring result space).

Simplifying It

This is like using a secret code (binary masks) to represent subsets. Each number from 0 to 2^n-1 is a code where ‘1’ means “include this item.” It’s super efficient and avoids recursion, making it great for larger arrays.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.