Pattern #22

Subsets / Power Set

Important interview questions, thinking patterns, 3 generation techniques (Backtracking, Iterative, Bitmask), and rules for solving power set problems in Go.

Must Solve

12 core questions — solve these first.

1.Subsets
Binary Take / Skip recursion or start index loopmedium
2.Subsets II
Sort array + skip same-level duplicates (i > start && nums[i] == nums[i-1])medium
3.Combination Sum
Backtracking with reusable choice (pass index i)medium
4.Combination Sum II
Sort + single-use choice (pass index i+1) + skip duplicatesmedium
5.Combinations
Choose K elements out of N using start indexmedium
6.Letter Case Permutation
Binary branch toggle uppercase / lowercasemedium
7.Generate Parentheses
Branch take open "(" vs take close ")"medium
8.Partition to K Equal Sum Subsets
Subset sum partitioning with K buckets & pruningmedium
9.Matchsticks to Square
4-side subset sum partitioning + sort descendingmedium
10.Maximum Length of a Concatenated String with Unique Characters
Bitmask / Subset recursion unique char checkmedium
11.Beautiful Arrangement
Divisibility check subset placement backtrackingmedium
12.Letter Tile Possibilities
Frequency map subset permutationsmedium

Also Important

8 more questions worth practicing.

13.Combination Sum III
Choose K digits from 1-9 summing to Nmedium
14.Palindrome Partitioning
Sub-string palindrome partition subsetsmedium
15.Restore IP Addresses
Partition string into 4 valid 0-255 subsetsmedium
16.Split a String Into the Max Number of Unique Substrings
HashSet seen unique substrings recursionmedium
17.Count Number of Maximum Bitwise-OR Subsets
Bitwise OR combination subsets countingmedium
18.Find Minimum Time to Finish All Jobs
Worker assignment subset search + binary searchhard
19.Fair Distribution of Cookies
Distribution of N cookie bags to K childrenmedium
20.Partition Equal Subset Sum
0/1 Knapsack DP or Subset Sum Backtrackingmedium

How to Think

Need every possible subset?Take / Skip ($2^N$ possibilities)
Each element can be chosen or ignored?Subsets
Need all combinations of elements?Backtracking
Input has duplicates?Sort + skip same-level duplicates
N is small and every combination matters?$2^N$ power set

Go Subsets Backtracking Template

Standard Subsets Backtracking in Go

func subsets(nums []int) [][]int {
    results := [][]int{}
    path := []int{}

    var dfs func(start int)
    dfs = func(start int) {
        // Save current path at EVERY node (since every subset is valid!)
        copyPath := append([]int(nil), path...)
        results = append(results, copyPath)

        for i := start; i < len(nums); i++ {
            path = append(path, nums[i])
            dfs(i + 1) // Move start index forward to prevent reverse duplicates [2,1]
            path = path[:len(path)-1] // Undo
        }
    }

    dfs(0)
    return results
}

👉 Total Time: O(N × 2^N) | Space: O(N) (Recursion depth = N)

3 Ways to Generate Subsets

1. Backtracking

Save current -> Choose next -> Recurse -> Undo

Most flexible for constraints, pruning, and custom rules.

2. Iterative

Start [[]] -> For num: Duplicate existing + append num

Doubles subset result size on every new element.

3. Bitmask

0 to (2^N)-1 -> bit 1 = Take, bit 0 = Skip

Ideal for small N (N <= 20) with fast bitwise operations.

Subsets II — Skipping Duplicates

When the input contains duplicate values (e.g. [1, 2, 2]), sort first and skip duplicate choices at the same recursion level:

sort.Ints(nums)

for i := start; i < len(nums); i++ {
    // Skip duplicate elements competing at the SAME recursion level!
    if i > start && nums[i] == nums[i-1] {
        continue
    }

    path = append(path, nums[i])
    dfs(i + 1)
    path = path[:len(path)-1]
}

Visual Memory Rule

N elements  →  2^N subsets (Every element asks: TAKE or SKIP?)
Start Index →  Prevents duplicate orderings like [1,2] and [2,1]
Duplicates  →  Sort first + skip same-level duplicates (i > start && nums[i] == nums[i-1])

💡 Golden Rule: "Every element asks one question: 'Do I take it, or do I skip it?'"

Common Interview Mistakes

1. Forgetting Empty Set []

The empty set [] is always a valid subset of the power set!

2. Confusing Subset with Subarray

Subsets can pick elements from anywhere ([1, 3] from [1, 2, 3]), whereas Subarrays MUST be contiguous!

3. Generating Duplicate Orders

Generating both [1, 2] and [2, 1] for subsets is wrong. Use start index to keep combinations forward-moving!

4. Not Copying Path in Go

Saving path without copy causes later backtracking pops to mutate saved subset results!

Interview Rules

1. Every possible subset? → Take / Skip Backtracking
2. N elements → 2^N total subsets
3. Empty set [] is included in the power set
4. Order does not matter ([1,2] is identical to [2,1])
5. Use start index to avoid order duplicates
6. Duplicate input? → Sort first + skip same-level duplicates
7. Every current path is a valid answer → Save during traversal
8. Overall Complexity → O(N × 2^N) time, O(N) space

Small Rules

Rule 1: Power set size is strictly 2^N.
Rule 2: Backtracking recursion depth is O(N).
Rule 3: Copying each subset of average size N/2 makes total work O(N × 2^N).
Rule 4: Subsets do not care about order; Permutations DO care about order.
Rule 5: Bitmask approach uses integers 0 to (2^N - 1) with bit 1 = Take, bit 0 = Skip.

Production Thinking

Product Feature Combinations → 4 optional features (Dark Mode, Push, Analytics, Offline) = 2^4 = 16 config subsets

API Permission Testing → Test all combinations of Read/Write/Delete/Admin role flags

Feature Flag Testing → Test 2^N feature flag enabled/disabled configurations

E-Commerce Search Filter Sets → Reason about active combinations of Price/Rating/Brand filters

Production Warning → Exponential explosion: N=20 is ~1 Million, N=30 is ~1 Billion subsets! Never generate power set for large N.

Remember This

Each element           → Take / Skip
n elements             → 2^n subsets
Subset                 → order doesn't matter
Empty set              → included
Backtracking           → save + choose + explore + undo
Duplicates             → sort + skip same level
Bitmask                → 0 skip, 1 take
Large n                → exponential explosion

💡 Golden Rule: "Every element asks one question: 'Do I take it, or do I skip it?'"