How to Solve: Generate All Subsets (Powerset) – Complete Guide for FAANG Interviews

How to Solve: Generate All Subsets (Powerset) – Complete Guide for FAANG Interviews

? Introduction

"This pattern appears in 1 out of every 3 onsite interviews—master it, and you’ll instantly stand out as a candidate who thinks in recursion, backtracking, and combinatorial logic."

? WHAT YOU NEED TO KNOW FIRST

Before tackling subsets, ensure you understand: 1. Recursion & Backtracking – How to build solutions incrementally and undo choices. 2. Bitmasking – Representing subsets as binary numbers (optional but powerful). 3. Time/Space Complexity of Recursive Calls – How to analyze exponential-time algorithms.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Follow these steps every time you see a "generate all subsets" problem:

1. Clarify the Problem
2. Are duplicates allowed in the input? (If yes, sort and skip duplicates.)
3. Should subsets be in a specific order? (If yes, sort the input first.)

4. Are there constraints on subset size? (If yes, modify recursion depth.)

5. Choose the Right Approach

6. Small input (n ≤ 20)? → Use bitmasking (iterative).
7. Large input or need recursion? → Use backtracking.

8. Duplicates in input? → Sort and skip duplicates in recursion.

9. Backtracking Template (Recursive)

10. Start with an empty subset (path = []).
11. For each element, include it in the subset, recurse, then exclude it (backtrack).

12. Base case: When all elements are processed, add the current subset to the result.

13. Bitmasking Template (Iterative)

14. Iterate from 0 to 2^n - 1 (each number represents a subset).

15. For each bit in the number, if set, include the corresponding element.

16. Optimize for Duplicates (If Needed)

17. Sort the input.

18. In recursion, skip duplicates by checking if i > start and nums[i] == nums[i-1].

19. Edge Cases

20. Empty input → Return [[]].
21. Single-element input → Return [[], [element]].

22. All duplicates → Ensure no duplicate subsets in the result.

23. Time & Space Complexity

24. Time: O(2^n) (since there are 2^n subsets).
25. Space: O(n) (recursion stack depth) or O(2^n) (if storing all subsets).

? WORKED EXAMPLES

Example 1 – Basic: Generate All Subsets (No Duplicates)

Problem: Given an integer array nums of unique elements, return all possible subsets (the powerset).

Thought Process

1. Clarify: No duplicates, no order constraints.
2. Approach: Backtracking (recursive).
3. Template:
4. Start with an empty subset.
5. For each element, include it, recurse, then exclude it (backtrack).

Solution Code (Python)

def subsets(nums):

    res = []

    def backtrack(start, path):

        res.append(path.copy())  # Add current subset

        for i in range(start, len(nums)):

            path.append(nums[i])  # Include nums[i]

            backtrack(i + 1, path)  # Recurse

            path.pop()  # Exclude nums[i] (backtrack)

    backtrack(0, [])

    return res

Complexity

• Time: O(2^n) (each element has 2 choices: include or exclude).
• Space: O(n) (recursion stack depth).

Why This Works

• We explore all possible combinations by including/excluding each element.
• start ensures we don’t reuse the same element multiple times (no duplicates in subsets).

Example 2 – Medium: Subsets with Duplicates

Problem: Given an integer array nums that may contain duplicates, return all possible subsets (the powerset). The solution set must not contain duplicate subsets.

Thought Process

1. Clarify: Duplicates allowed in input, but no duplicate subsets in output.
2. Approach: Backtracking + skip duplicates.
3. Key Insight: Sort the input first, then skip duplicates in recursion.

Solution Code (Python)

def subsetsWithDup(nums):

    nums.sort()  # Sort to handle duplicates

    res = []

    def backtrack(start, path):

        res.append(path.copy())

        for i in range(start, len(nums)):

            # Skip duplicates

            if i > start and nums[i] == nums[i-1]:

                continue

            path.append(nums[i])

            backtrack(i + 1, path)

            path.pop()

    backtrack(0, [])

    return res

Complexity

• Time: O(2^n) (worst case, but pruning reduces actual runtime).
• Space: O(n) (recursion stack).

Why This Works

• Sorting ensures duplicates are adjacent.
• if i > start and nums[i] == nums[i-1] skips duplicate subsets.

Example 3 – Hard/Follow-up: Subsets of Size K

Problem: Given an integer array nums of unique elements, return all possible subsets of size k.

Thought Process

1. Clarify: No duplicates, subsets must be of size k.
2. Approach: Backtracking with early termination.
3. Key Insight: Stop recursion when path reaches size k.

Solution Code (Python)

def subsetsOfSizeK(nums, k):

    res = []

    def backtrack(start, path):

        if len(path) == k:

            res.append(path.copy())

            return

        for i in range(start, len(nums)):

            path.append(nums[i])

            backtrack(i + 1, path)

            path.pop()

    backtrack(0, [])

    return res

Complexity

• Time: O(C(n, k)) (combinations of n choose k).
• Space: O(k) (recursion depth).

Why This Works

• We only add subsets of size k to the result.
• Early termination avoids unnecessary recursion.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. When you see ‘generate all subsets,’ remember:

1. Backtracking is your default. Start with an empty subset, include/exclude each element, and recurse.
2. Sort first if duplicates exist. Skip duplicates in recursion to avoid redundant subsets.
3. Bitmasking is a neat trick for small inputs. Iterate from 0 to 2^n - 1 and check bits.
4. Edge cases matter. Empty input? Single element? All duplicates? Handle them explicitly.
5. Time complexity is always O(2^n). Don’t overthink it—this is the best you can do.

Now go crush that interview. You’ve got this!

? Final Notes

• Practice Variations:
• Subsets with sum constraints (e.g., "all subsets that sum to k").
• Subsets with unique elements (e.g., "all subsets where no two elements are adjacent").
• Whiteboard Tip: Draw the recursion tree to visualize backtracking.
• Follow-up Question: "How would you generate subsets in lexicographic order?" → Sort the input first.

This guide is 100% interview-ready—use it as a checklist, and you’ll never blank on a subsets problem again. ?