Generate All Subsets — The Power Set Pattern Every Backtracking Problem Builds On

Problem Statement#

Given an integer array nums, return all possible subsets (the power set). The solution set must not contain duplicate subsets and may be returned in any order. LeetCode 78 has unique elements; LeetCode 90 (Subsets II) allows duplicates in the input.

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All elements unique for LC 78; possibly duplicate for LC 90

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

Input:  nums = [1, 2, 2]   (LC 90)
Output: [[], [1], [1,2], [1,2,2], [2], [2,2]]

Why This Problem Matters#

Subsets is the canonical backtracking warmup. Amazon, Google, and Meta all use it to verify that a candidate has internalized the choose-explore-unchoose rhythm before moving on to harder constraint problems like N-Queens or Combination Sum II. If you cannot produce subsets cleanly in five minutes, the rest of the loop becomes a stress test instead of a conversation.

The same template you learn here powers feature selection in machine learning, generating all test configurations in QA tools, enumerating team compositions in scheduling systems, and even brute-force solvers for small SAT instances. Every "generate all selections" problem in the wild reduces to this template plus a problem-specific pruning rule.

The duplicate-skip technique introduced in Subsets II reappears identically in Combination Sum II, Permutations II, and any backtracking problem with repeated input. Internalizing it once means you apply it automatically forever after.

The Core Insight#

For each element you face a binary decision: include it in the current subset or skip it. Making this choice independently for n elements yields exactly 2^n subsets — the size of the power set. The decision tree has depth n and a branching factor of two at every node.

The cleanest implementation uses a start index. At each recursive call you iterate from start to the end. For each i, you include nums[i], recurse with i+1 as the new start (so you never revisit earlier elements), then pop nums[i] to backtrack. Crucially you record a snapshot at every node — not just leaves — because every partial path is itself a valid subset.

For duplicates (LC 90) sort the array first, then inside the loop skip nums[i] if i > start and nums[i] == nums[i-1]. The i > start condition restricts skipping to siblings at the same level, which is exactly where duplicate subtrees would form.

Visual Dry Run#

Input nums = [1, 2, 3]:

For nums = [1, 2, 2] after sorting, skipping i=2 when i > start=0 and nums[2]==nums[1] removes the duplicate branch starting at the second 2.

Solution (Optimal)#

class Solution:
    def subsets(self, nums):
        result = []
 
        def bt(start, current):
            # Record the current subset at every node, not only at leaves
            result.append(current[:])  # snapshot copy, not reference
 
            for i in range(start, len(nums)):
                current.append(nums[i])  # CHOOSE
                bt(i + 1, current)       # EXPLORE — never revisit earlier indices
                current.pop()            # UNCHOOSE
 
        bt(0, [])
        return result
 
    def subsetsWithDup(self, nums):
        nums.sort()  # adjacency is required for duplicate-skip
        result = []
 
        def bt(start, current):
            result.append(current[:])
 
            for i in range(start, len(nums)):
                # Skip duplicate siblings: same value at same recursion level
                if i > start and nums[i] == nums[i - 1]:
                    continue
                current.append(nums[i])
                bt(i + 1, current)
                current.pop()
 
        bt(0, [])
        return result

var subsets = function(nums) {
    const result = [];
 
    const bt = (start, current) => {
        result.push([...current]); // snapshot via spread
 
        for (let i = start; i < nums.length; i++) {
            current.push(nums[i]);  // CHOOSE
            bt(i + 1, current);     // EXPLORE
            current.pop();          // UNCHOOSE
        }
    };
 
    bt(0, []);
    return result;
};
 
var subsetsWithDup = function(nums) {
    nums.sort((a, b) => a - b);
    const result = [];
 
    const bt = (start, current) => {
        result.push([...current]);
 
        for (let i = start; i < nums.length; i++) {
            // Skip duplicate siblings only — `i > start` restricts to same level
            if (i > start && nums[i] === nums[i - 1]) continue;
            current.push(nums[i]);
            bt(i + 1, current);
            current.pop();
        }
    };
 
    bt(0, []);
    return result;
};

Time: O(2^n * n) for both LC 78 and LC 90. There are up to 2^n subsets and copying each one takes O(n). Space: O(n) recursion depth plus O(2^n * n) for the output.

Common Mistakes#

• Recording only at leaves — produces only full-length subsets, missing all shorter ones
• Pushing current instead of a snapshot — every stored entry mutates as backtracking progresses
• Writing nums[i] == nums[i-1] without i > start — incorrectly skips first occurrences in branches
• Forgetting to sort before applying the duplicate-skip rule
• Confusing subsets with combinations — LC 77 needs an exact size check that LC 78 must not include

Interview Tips#

• State the 2^n decision tree before coding so the interviewer sees you understand the shape
• Explain why the snapshot copy is necessary even if it feels obvious
• For LC 90 mention the sort first, then articulate why i > start is the correct condition
• Mention the bitmask alternative for n <= 20 as a depth signal
• Walk through the small example by hand if time permits — it always catches off-by-one bugs

Follow-up Questions#

• How does the bitmask approach work? Hint: iterate masks 0 to 2^n-1 and bit i set means include nums[i].
• What if you want subsets of exactly size k? Hint: combine the size check with bound pruning on remaining capacity.
• Can you generate subsets iteratively without recursion? Hint: start with [[]] and double the result by appending each new number.
• How do you count subsets with sum equal to target? Hint: 0/1 knapsack DP, not backtracking.
• How does this generalize to multiset subsets? Hint: per-value counts plus a recursion over distinct values.

Key Takeaways#

• Subsets uses include-exclude with a start index and records at every node
• Always snapshot via current[:] in Python or [...current] in JavaScript
• LC 90 requires sort plus i > start && nums[i] == nums[i-1] to dedupe siblings
• Recursion depth is O(n); output dominates space at O(2^n * n)
• The bitmask alternative is iterative, equally fast, and signals depth in interviews
• Subset enumeration is the foundation for combinations, permutations, and partitioning
• Mastering the choose-explore-unchoose rhythm here unlocks the entire backtracking family