Subsets

An Interactive Visual Explainer

Idea By: Chetan Pachpande | Executed By: Gemini
Back to Home

Problem Description

Given an array `nums` of **unique** integers, return all possible subsets of `nums`.

The solution set must **not** contain duplicate subsets. You may return the solution in **any order**.

Example 1:

Input: nums = [1,2,3]

Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [7]

Output: [[],[7]]

Complexity Analysis

Time Complexity: O(N * 2^N)

We generate 2^N subsets. For each subset, we create a new list, which can take up to O(N) time. This results in N * 2^N total operations.

Space Complexity: O(N)

The recursion depth is at most N, which dominates the space used by the call stack.

Intuition

The core idea is to build the subsets incrementally using a recursive technique called **backtracking**. Imagine a decision tree. At each level of the tree, we are deciding whether to include the current number `nums[i]` in our subset or not.

  1. The Choice: For each element in `nums`, we have two choices: either **include** it in the current subset or **skip** it.
  2. Explore: We start with an empty subset. We then iterate through the `nums` array. For each number, we add it to our current subset and then recursively call our function to generate all further subsets that can be formed with this new addition.
  3. Backtrack: This is the crucial step. After the recursive call returns (meaning it has explored all possibilities with the number included), we **remove** that number from our current subset. This "backtracking" allows us to explore the path where the number was *not* included, enabling us to generate all possible combinations.

Step-by-Step Code

Live Visualization & Controls

Decision Tree


                        

                    

                    

                        
Result Subsets

                        

                    

                

                
                

                    
Algorithm States

                    

                        

                            Status: Idle
                            Current Index (i): N/A
                            Current Subset: []
                        

                    

                

                
                

                    
Call Stack

                    

                        
Stack is empty

                    

                


                

                     
Execution Controls