logoNEURAL COOK
SearchAll PostsTagsNotesAuthor
logoNEURAL COOK

A posts created with Next.js and Tailwind.css

Explore

  • All posts
  • Notes
  • Snippets
  • Tags
  • RSS feed

Connect

instagramtwitterfacebookyoutubelinkedinmailgithub

© 2026 VIKI. All rights reserved.

Built with
Contents
Table Of Contents
Generate ParenthesesPower Function: pow(x, n)Subsets (The Power Set)
Code Scratch/take u forward/recursion/implementation problems

Subsets (The Power Set)

8 min read
On this pageQuestion
QuestionSolutionPatternHow to IdentifyDescriptionThe IntuitionComplexityCodeConcepts to Think AboutLogical Follow-upSolution (Bit Masking Approach)PatternHow to IdentifyDescriptionThe IntuitionComplexityCodeWhen to AVOID BitmaskingConcepts to Think AboutLogical Follow-up

# Question

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

# Solution

# Pattern

Backtracking (Decision Tree) The problem follows the "Pick or Don't Pick" pattern. For every element in the array, we have a binary choice: either include it in the current subset or exclude it.

# How to Identify

  • The problem asks for "All Possible" configurations (subsets, permutations, combinations).
  • The input size nnn is small (typically n < 20), as the result grows exponentially.
  • The problem involves building a result incrementally by making a series of choices.

# Description

We use a recursive helper function to explore a decision tree.

  1. The Choice: At each index iii in the array, we decide:
    • Path A: Include nums[i]nums[i]nums[i] in the current subset and move to i+1i+1i+1.
    • Path B: Do not include nums[i]nums[i]nums[i] and move to i+1i+1i+1.
  2. Base Case: When our current index reaches nums.lengthnums.lengthnums.length, it means we have made a choice for every element. We take a "snapshot" of our current subset and add it to our global result list.
  3. Backtracking: To ensure Path B doesn't contain elements from Path A, we must remove the element we just added before returning from the recursive call. This "cleans up" the state.

# The Intuition

Think of the Power Set as a Binary String of length nnn.

  • Each bit represents an element in the array.
  • A 1 means "Included," and a 0 means "Excluded."
  • Since there are 2n2^n2n possible binary strings of length nnn, there are 2n2^n2n subsets.

This mental model helps you realize that the subsets problem is actually a search through the space of all possible nnn-bit combinations.

# Complexity

LabelWorstAverage
Time ComplexityO(n⋅2n)O(n \cdot 2^n)O(n⋅2n)O(n⋅2n)O(n \cdot 2^n)O(n⋅2n)
Space ComplexityO(n⋅2n)O(n \cdot 2^n)O(n⋅2n)O(n⋅2n)O(n \cdot 2^n)O(n⋅2n)

# Time Complexity

There are 2n2^n2n subsets. For each subset, we spend O(n)O(n)O(n) time to create a copy of the current list and add it to the result.

# Space Complexity

The output requires O(n⋅2n)O(n \cdot 2^n)O(n⋅2n) space. The recursion stack depth is O(n)O(n)O(n), and the temporary list used for backtracking also takes O(n)O(n)O(n).

# Code

class Solution {
    public List&lt;List<Integer&gt;&gt; subsets(int[] nums) {
        List&lt;List&lt;Integer&gt;&gt; result = new ArrayList<>();
        // Start backtracking from index 0
        backtrack(result, new ArrayList<>(), nums, 0);
        return result;
    }
 
    private void backtrack(List&lt;List&lt;Integer&gt;&gt; result, List&lt;Integer&gt; current, int[] nums, int index) {
        // Base Case: We've considered all elements
        if (index == nums.length) {
            // Must create a new copy because current is modified in place
            result.add(new ArrayList<>(current));
            return;
        }
 
        // Decision 1: Include the current element
        current.add(nums[index]);
        backtrack(result, current, nums, index + 1);
 
        // Decision 2: Exclude the current element (Backtrack)
        current.remove(current.size() - 1);
        backtrack(result, current, nums, index + 1);
    }
}

# Concepts to Think About

  • Bitmasking: You can generate subsets by iterating from 000 to 2n−12^n - 12n−1 and using the bit representation of the counter to pick elements.
  • Lexicographical Order: The recursive approach naturally generates subsets in a specific order (DFS order).
  • Copying Overhead: O(n)O(n)O(n) copying at the base case is unavoidable if you want to return a list of lists.
  • Space Optimization: If you only need to process subsets rather than return them, space drops to O(n)O(n)O(n).
  • Gray Code: A specialized sequence of 2n2^n2n bitstrings where each adjacent string differs by only one bit. This can be used to generate subsets by adding/removing exactly one element at a time.

# Logical Follow-up

Question: Subsets II: What if the input array nums contains duplicates? How do you ensure the power set contains no duplicate subsets?

Solution:

  1. Sort the array: This brings duplicates together.
  2. Handle Duplicates in Backtracking: When choosing not to include an element, you must skip all subsequent occurrences of that same element.
    • Logic: while (index + 1 &lt; nums.length && nums[index] == nums[index + 1]) index++;
    • This ensures you don't start a new decision branch with a value you've already rejected for that specific position.

Question: Memory Constraints: If n=30n = 30n=30, 2302^{30}230 is over a billion. You cannot return this in a List. How would you handle this in a real system?

Solution: At a Google scale, we would use an Iterator pattern or a Generator. Instead of storing all subsets, we provide a next() method that calculates the next subset on the fly (perhaps using the bitmasking approach). This keeps space at O(n)O(n)O(n).

# Solution (Bit Masking Approach)

# Pattern

Bit Manipulation (Binary Mapping) Treat each subset as a binary number of length nnn, where the jthj^{th}jth bit represents whether nums[j]nums[j]nums[j] is included in the subset.

# How to Identify

  • You need to generate all combinations of a set.
  • The total number of results is exactly 2n2^n2n.
  • Each element has a simple binary state: Included (111) or Excluded (000).
  • You want to avoid the overhead of a recursive call stack.

# Description

We iterate through every possible integer from 000 up to 2n−12^n - 12n−1.

  1. The Loop: For an array of size nnn, there are 2n2^n2n total subsets. We run a loop from i=0i = 0i=0 to 2n−12^n - 12n−1.
  2. The Mask: Each value of iii is a "mask." For example, if n=3n=3n=3, the mask 555 is 101 in binary.
  3. Bit Checking: For each mask, we check every bit position jjj (from 000 to n−1n-1n−1):
    • If the jthj^{th}jth bit is set (111), we include nums[j]nums[j]nums[j] in the current subset.
    • If the jthj^{th}jth bit is not set (000), we skip it.
  4. Efficiency: We use bitwise shifts 1 &lt;< n to calculate 2n2^n2n and (i &gt;&gt; j) & 1 to check bits.

# The Intuition

Imagine nnn light switches. Each configuration of switches (on/off) represents a unique subset. Since each switch has 222 states, nnn switches have 2n2^n2n configurations. If we count from 000 to 2n−12^n - 12n−1 in binary, we are essentially cycling through every possible configuration of those light switches. We are simply "reading" the binary state of the counter to decide what goes into our "suitcase."

# Complexity

LabelWorstAverage
Time ComplexityO(n⋅2n)O(n \cdot 2^n)O(n⋅2n)O(n⋅2n)O(n \cdot 2^n)O(n⋅2n)
Space ComplexityO(1)O(1)O(1)O(1)O(1)O(1)

# Time Complexity

The outer loop runs 2n2^n2n times. The inner loop runs nnn times to check each bit. Total: O(n⋅2n)O(n \cdot 2^n)O(n⋅2n).

# Space Complexity

Excluding the space for the result list, the auxiliary space is O(1)O(1)O(1) because we only use a few integer variables. There is no recursion stack.

# Code

class Solution {
    public List&lt;List&lt;Integer&gt;&gt; subsets(int[] nums) {
        List&lt;List&lt;Integer&gt;&gt; result = new ArrayList<>();
        int n = nums.length;
 
        // Total subsets = 2^n
        int totalSubsets = 1 &lt;&lt; n;
 
        for (int i = 0; i < totalSubsets; i++) {
            List<Integer&gt; currentSubset = new ArrayList<&gt;();
 
            // Check each bit of the current number 'i'
            for (int j = 0; j &lt; n; j++) {
                // If the j-th bit is set, include nums[j]
                if (((i &gt;> j) & 1) == 1) {
                    currentSubset.add(nums[j]);
                }
            }
            result.add(currentSubset);
        }
 
        return result;
    }
}

# When to AVOID Bitmasking

Even though it's "cleaner," an experienced developer knows when to stick to backtracking:

  • If n>30n > 30n>30: An int only has 31 usable bits. If n=40n = 40n=40, you need a long. If n=100n = 100n=100, bitmasking is impossible.
  • If there are Duplicates: Handling "Subsets II" (unique subsets from a duplicate array) is very natural in backtracking but requires complex hash-sets or logic in bitmasking.
  • If Pruning is needed: If the problem is "Subsets that sum to KKK," backtracking can stop early if the current sum exceeds KKK. Bitmasking must check all 2n2^n2n possibilities regardless.

# Concepts to Think About

  • Power of Two: 1 &lt;&lt; n is an extremely fast way to calculate 2n2^n2n.
  • Bitwise AND: (i & (1 << j)) is an alternative to (i &gt;&gt; j) & 1 for checking if the jthj^{th}jth bit is set.
  • Limit of int: This approach only works if n<31n < 31n<31. If n≥31n \geq 31n≥31, 2n2^n2n will overflow a 32-bit int. You would need a long (up to n=63n = 63n=63) or BigInteger.
  • Lexicographical Order: Bitmasking generates subsets in a different order than DFS-based backtracking. Backtracking is usually "depth-first," while bitmasking is "numerical order" of the masks.
  • Cache Locality: Iterative solutions are often more cache-friendly than recursive ones because they don't jump around the memory stack as much.

# Logical Follow-up

Question: Constant Space Processing: If you are asked to print all subsets but are forbidden from using more than O(n)O(n)O(n) space total (no result list), how does Bitmasking help?

Solution: Since Bitmasking is iterative, you can generate and print each subset one by one in the inner loop. Once a subset is printed, you can clear the currentSubset list or just print directly from the array. This keeps the total space complexity at O(n)O(n)O(n) for the temporary storage, compared to O(n⋅2n)O(n \cdot 2^n)O(n⋅2n) if you were forced to store them all.

Question: Subset of a Specific Size: How would you modify the bitmask approach to only return subsets of size kkk?

Solution: Inside the inner loop, you would use Integer.bitCount(i) to check if the current mask has exactly kkk bits set to 1. If it does, you process it; otherwise, you skip it. Note that while this works, it is less efficient than a specialized backtracking approach because you still iterate 2n2^n2n times.

←PreviousPower Function: pow(x, n)Next→Subsequence Sum Existence

On this page

QuestionSolutionPatternHow to IdentifyDescriptionThe IntuitionComplexityCodeConcepts to Think AboutLogical Follow-upSolution (Bit Masking Approach)PatternHow to IdentifyDescriptionThe IntuitionComplexityCodeWhen to AVOID BitmaskingConcepts to Think AboutLogical Follow-up