Problem Description

You are given an integer array nums that contains unique elements (no duplicates). Your task is to generate and return all possible subsets of this array, also known as the power set.

A subset is a collection that can be formed by including or excluding each element from the original array. The empty subset (containing no elements) and the full array itself are both valid subsets.

Important requirements:

• The solution must include all possible subsets - from the empty set to the full array
• There should be no duplicate subsets in your result
• The subsets can be returned in any order

For example, if nums = [1, 2, 3], the power set would be:

• [] (empty subset)
• [1]
• [2]
• [3]
• [1, 2]
• [1, 3]
• [2, 3]
• [1, 2, 3] (full array)

The total number of subsets for an array of n elements is always 2^n, since each element has two choices: either be included in the subset or not.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem does not involve nodes and edges or graph traversal. We're working with an array of integers and need to generate subsets.

Need to solve for kth smallest/largest?

• No: We're not looking for a specific kth element. We need to generate all possible subsets.

Involves Linked Lists?

• No: The problem works with an array, not linked lists.

Does the problem have small constraints?

• Yes: Generating all subsets means we need to explore 2^n possibilities. This exponential growth is only feasible with small constraints (typically n ≤ 20). The problem asks us to generate ALL possible combinations, which inherently suggests manageable input sizes.

Brute force / Backtracking?

• Yes: Since we need to explore all possible combinations of including or excluding each element, backtracking is the perfect approach. For each element, we make a choice (include it or not), explore further, and then backtrack to explore other possibilities.

Conclusion: The flowchart correctly leads us to use a Backtracking approach. This makes sense because:

• We need to generate all possible combinations (exhaustive search)
• Each element has a binary choice (include/exclude)
• We can build solutions incrementally and backtrack when needed
• The problem space forms a decision tree where we explore all paths

Intuition

The key insight for generating all subsets is recognizing that for each element in the array, we have exactly two choices: either include it in the current subset or exclude it. This binary decision-making process naturally forms a decision tree.

Imagine you're packing for a trip and have n items. For each item, you decide: "take it" or "leave it". After making decisions for all items, you have one possible packing configuration (subset). To find all possible configurations, you'd need to explore every combination of decisions.

This is exactly what the backtracking solution does. Starting from index 0, we:

1. First explore the path where we don't include the current element (just move to the next index)
2. Then explore the path where we do include the current element (add it to our current subset, then move to the next index)

The beauty of this approach is that it naturally builds a complete decision tree. Each leaf node in this tree represents a complete subset (after we've made decisions for all elements). Since we have n elements and 2 choices for each, we get 2^n total subsets.

The backtracking happens when we've explored one branch completely - we remove the element we just added (the t.pop() operation) to restore our subset to its previous state, allowing us to explore other branches from that point.

Think of it like exploring a maze where at each intersection you can go left (exclude) or right (include). You systematically explore all paths: first go left at every intersection until you reach the end, record that path, then backtrack and try going right at the last intersection, and so on, until you've mapped every possible route through the maze.

Learn more about Backtracking patterns.

Solution Approach

The implementation uses a DFS (Depth-First Search) with backtracking to generate all subsets. Let's walk through the key components:

Core Algorithm Structure:

We define a recursive function dfs(i) that processes elements starting from index i. This function represents our decision point for the element at position i in the array.

Base Case: When i == len(nums), we've made decisions for all elements. At this point, we add a copy of the current subset t to our answer array ans. We use t[:] to create a copy because t will continue to be modified as we backtrack.

Recursive Cases: For each element at index i, we explore two branches:

1. Exclude the current element: We directly call dfs(i + 1) without adding nums[i] to our subset. This explores all subsets that don't contain nums[i].

2. Include the current element: We add nums[i] to our current subset t using t.append(nums[i]), then call dfs(i + 1) to explore all subsets that contain nums[i].

Backtracking Step: After exploring the "include" branch, we need to restore our subset to its previous state. We do this with t.pop(), which removes the element we just added. This is crucial - it allows us to backtrack to the previous decision point and explore other possibilities.

Data Structures Used:

• ans: A list to store all generated subsets
• t: A temporary list that represents the current subset being built
• The recursion stack implicitly maintains our position in the decision tree

Execution Flow: Starting with dfs(0), the algorithm systematically explores all 2^n paths through the decision tree. Each path from root to leaf represents one unique subset, ensuring we generate all possible combinations without duplicates.

The time complexity is O(n × 2^n) since we generate 2^n subsets and each subset operation (copying) takes O(n) time. The space complexity is O(n) for the recursion stack depth.

Example Walkthrough

Let's trace through the algorithm with nums = [1, 2, 3] to see how it generates all 8 subsets.

We start with an empty temporary subset t = [] and call dfs(0).

Step-by-step execution:

1. dfs(0) - Deciding on element 1:

   • First, exclude 1: call dfs(1) with t = []

2. dfs(1) - Deciding on element 2 (with 1 excluded):

   • First, exclude 2: call dfs(2) with t = []

3. dfs(2) - Deciding on element 3 (with 1,2 excluded):

   • First, exclude 3: call dfs(3) with t = []

4. dfs(3) - Base case reached: Add [] to answer ✓

   • Backtrack to dfs(2)
   • Now include 3: t = [3], call dfs(3)

5. dfs(3) - Base case: Add [3] to answer ✓

   • Pop 3, backtrack to dfs(1)
   • Now include 2: t = [2], call dfs(2)

6. dfs(2) - Deciding on element 3 (with 2 included):

   • First, exclude 3: call dfs(3) with t = [2]

7. dfs(3) - Base case: Add [2] to answer ✓

   • Backtrack to dfs(2)
   • Now include 3: t = [2, 3], call dfs(3)

8. dfs(3) - Base case: Add [2, 3] to answer ✓

   • Pop 3, then pop 2, backtrack to dfs(0)
   • Now include 1: t = [1], call dfs(1)

9. dfs(1) - Deciding on element 2 (with 1 included):

   • First, exclude 2: call dfs(2) with t = [1]

10. dfs(2) - Deciding on element 3 (with 1 included, 2 excluded):

    • First, exclude 3: call dfs(3) with t = [1]

11. dfs(3) - Base case: Add [1] to answer ✓

    • Backtrack to dfs(2)
    • Now include 3: t = [1, 3], call dfs(3)

12. dfs(3) - Base case: Add [1, 3] to answer ✓

    • Pop 3, backtrack to dfs(1)
    • Now include 2: t = [1, 2], call dfs(2)

13. dfs(2) - Deciding on element 3 (with 1,2 included):

    • First, exclude 3: call dfs(3) with t = [1, 2]

14. dfs(3) - Base case: Add [1, 2] to answer ✓

    • Backtrack to dfs(2)
    • Now include 3: t = [1, 2, 3], call dfs(3)

15. dfs(3) - Base case: Add [1, 2, 3] to answer ✓

Final Result: [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]

The decision tree visualization:

                     Start (i=0, t=[])
                    /                  \
            Exclude 1                Include 1
           (i=1, t=[])              (i=1, t=[1])
           /         \              /           \
      Exclude 2   Include 2    Exclude 2    Include 2
     (i=2,t=[])  (i=2,t=[2])  (i=2,t=[1]) (i=2,t=[1,2])
       /   \       /    \        /    \       /      \
      []   [3]   [2]  [2,3]    [1]  [1,3]  [1,2]  [1,2,3]

Each path from root to leaf represents one subset. The backtracking ensures we explore all branches systematically, generating all 2³ = 8 possible subsets.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × 2^n)

The algorithm explores a binary decision tree where at each level i, we decide whether to include nums[i] in the current subset or not. This creates 2^n total subsets (where n is the length of the input array). For each subset, when we reach the base case (i == len(nums)), we perform a copy operation t[:] which takes O(n) time to create a copy of the current subset. Therefore, the total time complexity is O(n × 2^n).

Space Complexity: O(n)

The space complexity consists of:

• The recursion call stack depth, which can go up to n levels deep (one for each element in nums)
• The temporary list t which stores the current subset being constructed, having at most n elements
• The output list ans is not counted as part of the auxiliary space complexity since it's required for the output

The dominant factor is the recursion depth and the temporary list, both of which are O(n). Note that while the total output requires O(n × 2^n) space to store all subsets, the auxiliary space complexity (excluding output) is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Create a Copy of the Current Subset

The Pitfall: One of the most common mistakes is adding the current subset directly to the result without creating a copy:

# WRONG - This will cause all subsets to reference the same list
if index == len(nums):
    result.append(current_subset)  # ❌ Direct reference
    return

Why This Fails: Since current_subset is a mutable list that gets modified throughout the recursion, all entries in result will end up pointing to the same list object. By the end of execution, result will contain multiple references to an empty list.

The Solution: Always create a copy of the current subset before adding it to the result:

# CORRECT - Creates a new list with the current elements
if index == len(nums):
    result.append(current_subset[:])  # ✅ Creates a copy
    # Alternative ways to copy:
    # result.append(list(current_subset))
    # result.append(current_subset.copy())
    return

2. Forgetting the Backtracking Step

The Pitfall: Another critical error is forgetting to remove the element after exploring the "include" branch:

# WRONG - Missing the pop() operation
backtrack(index + 1)
current_subset.append(nums[index])
backtrack(index + 1)
# ❌ Forgot to pop the element!

Why This Fails: Without removing the element, the current_subset will keep accumulating elements from different branches of the decision tree. This corrupts the subset generation process and produces incorrect results.

The Solution: Always restore the state after exploring a branch:

# CORRECT - Properly backtrack after exploring
backtrack(index + 1)
current_subset.append(nums[index])
backtrack(index + 1)
current_subset.pop()  # ✅ Essential backtracking step

3. Incorrect Order of Operations

The Pitfall: Placing the recursive calls in the wrong order relative to the append/pop operations:

# WRONG - Append before both recursive calls
current_subset.append(nums[index])
backtrack(index + 1)  # This explores with element included
backtrack(index + 1)  # This also has element included!
current_subset.pop()

Why This Fails: Both recursive calls will explore subsets that include nums[index], missing all subsets that exclude this element.

The Solution: Follow the correct pattern: exclude first, then include-explore-backtrack:

# CORRECT - Proper order of operations
backtrack(index + 1)  # Explore without current element
current_subset.append(nums[index])
backtrack(index + 1)  # Explore with current element
current_subset.pop()  # Backtrack