Skip to main content
CodePeetCodePeet
CodePeet 150

Subsets

MEDIUMProblemSolveExternal Links

Description

You are given an integer array nums where every element is unique. Your task is to return all possible subsets of the array, also known as the power set.

A subset is any selection of elements from the array (including selecting none of them, which gives the empty set, or selecting all of them). The order of elements within a subset does not matter, and the result must not contain duplicate subsets.

Return the solution in any order.

Examples

Example 1

Input: nums = [1, 2, 3]

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

Explanation: There are 2³ = 8 total subsets for an array of length 3. Each element can either be included or excluded from a subset. The empty set [] is always a valid subset. The full array [1, 2, 3] is also a valid subset. Every combination of included/excluded elements between these extremes is listed.

Example 2

Input: nums = [0]

Output: [[], [0]]

Explanation: A single-element array has exactly 2¹ = 2 subsets: the empty set and the set containing the single element.

Example 3

Input: nums = [5, 9]

Output: [[], [5], [9], [5, 9]]

Explanation: For two elements, there are 2² = 4 subsets: exclude both (empty), include only the first, include only the second, or include both.

Constraints

  • 1 ≤ nums.length ≤ 10
  • -10 ≤ nums[i] ≤ 10
  • All the numbers of nums are unique.

Editorial

Brute Force - Iterative Subset Construction

Intuition

The most natural way to think about generating all subsets is to build them up one element at a time.

Imagine you have a collection box that starts with just one item inside: an empty bag. Now you pick up the first element from the array. You look at every bag currently in the box, create a copy of each, drop the element into each copy, and place all those new bags back into the box.

Before processing element 1, you had one bag: []. After processing, you have two bags: [] and [1]. Now pick up element 2. Clone every bag and put 2 in the clones: [] becomes [2], [1] becomes [1, 2]. Add both to the box. You now have four bags: [], [1], [2], [1, 2].

Repeat for every element. Each round doubles the number of subsets, because every existing subset spawns a new version that includes the current element. After processing all n elements, you have exactly 2ⁿ subsets — the complete power set.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3]:

Step 1: Initialize the result with one subset — the empty set.

  • result = [ [] ]

Step 2: Process element 1 (index 0). We have 1 existing subset. Clone it and append 1.

  • Clone [] → add 1 → [1]
  • result = [ [], [1] ]

Step 3: Process element 2 (index 1). We have 2 existing subsets. Clone each and append 2.

  • Clone [] → add 2 → [2]
  • Clone [1] → add 2 → [1, 2]
  • result = [ [], [1], [2], [1, 2] ]

Step 4: Process element 3 (index 2). We have 4 existing subsets. Clone each and append 3.

  • Clone [] → add 3 → [3]
  • Clone [1] → add 3 → [1, 3]
  • Clone [2] → add 3 → [2, 3]
  • Clone [1, 2] → add 3 → [1, 2, 3]
  • result = [ [], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3] ]

Result: 8 subsets generated. 2³ = 8 ✓

Iterative Cascading — Building the Power Set — Watch how each new element doubles the number of subsets by cloning every existing subset and appending the current element to each clone.

Algorithm

  1. Initialize the result list with one element: the empty set []
  2. For each element num in the input array:
    a. Record the current size of the result list as size
    b. For each existing subset at index j from 0 to size - 1:
    • Clone the subset at result[j]
    • Append num to the cloned subset
    • Add the new subset to the result list
  3. Return the result list containing all 2ⁿ subsets

Code

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        result.push_back({});  // start with empty subset
        
        for (int num : nums) {
            int size = result.size();
            for (int j = 0; j < size; j++) {
                vector<int> newSubset = result[j];  // clone
                newSubset.push_back(num);            // extend
                result.push_back(newSubset);         // add
            }
        }
        
        return result;
    }
};
class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        result = [[]]  # start with empty subset
        
        for num in nums:
            # clone each existing subset and append num
            new_subsets = [subset + [num] for subset in result]
            result.extend(new_subsets)
        
        return result
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());  // start with empty subset
        
        for (int num : nums) {
            int size = result.size();
            for (int j = 0; j < size; j++) {
                List<Integer> newSubset = new ArrayList<>(result.get(j));
                newSubset.add(num);
                result.add(newSubset);
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n × 2ⁿ)

There are 2ⁿ subsets in total. For each of the n elements, we iterate over all existing subsets and clone each one. At step k, there are 2ᵏ subsets, and each clone takes up to O(k) time. Summing across all steps gives O(n × 2ⁿ).

Space Complexity: O(n × 2ⁿ)

We store all 2ⁿ subsets in the result list. Each subset has an average length of n/2, so total space for the output is O(n × 2ⁿ). Additionally, each cloning step creates temporary copies, adding further O(n × 2ⁿ) intermediate allocation overhead.

Why This Approach Is Not Efficient

While the iterative cascading approach correctly generates all subsets, it has practical drawbacks:

1. Excessive intermediate copies: At each step, every existing subset is cloned (copied element-by-element) before the new element is appended. For step k, this means cloning 2ᵏ subsets of average size k/2, costing O(k × 2ᵏ) copy work. Summed over all n steps, the total copying overhead is O(n × 2ⁿ) — in addition to the output storage itself.

2. Poor generalization: If we later need to generate subsets with constraints (e.g., Subsets II with duplicates, Combination Sum, Permutations), the iterative approach requires significant restructuring. It does not naturally support pruning or constraint checking mid-generation.

3. Memory pressure: All subsets exist simultaneously in memory throughout the construction process. For large n, this puts pressure on the memory allocator.

A better strategy is backtracking using the include/exclude pattern. Backtracking explores one branch of the decision tree at a time, uses only O(n) auxiliary space for the recursion stack and current subset, and naturally supports pruning. It also teaches the foundational pattern used across dozens of related problems (Subsets II, Combinations, Permutations, N-Queens).

Optimal Approach - Backtracking with Include/Exclude Pattern

Intuition

Think of building a subset as making a series of yes/no decisions. For each element in the array, you ask yourself one question: "Should I include this element in my current subset, or should I skip it?"

Imagine standing at a buffet with 3 dishes labeled 1, 2, and 3. At each dish, you decide: take it or leave it. After passing all 3 dishes, whatever is on your plate is one complete subset. If you could magically split into two copies of yourself at each dish — one that takes the food and one that skips it — you would end up with 2³ = 8 versions of yourself, each holding a different subset.

This is exactly what backtracking does. It uses recursion to explore both branches (include and exclude) at each decision point. When it reaches the end of the array, it records whatever is currently in the subset. Then it backtracks — undoes the last inclusion — and explores the other branch.

The beauty of this approach is that it only maintains one subset at a time (the "current" one being built), keeping auxiliary space to O(n). It also naturally generalizes to constrained problems: you simply add a condition before the include branch to prune invalid choices.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3] using backtrack(index, current):

Step 1: Call backtrack(0, []). We're at element 1 — decide: include or exclude?

Step 2: Include 1 → current = [1]. Call backtrack(1, [1]).

Step 3: Include 2 → current = [1, 2]. Call backtrack(2, [1, 2]).

Step 4: Include 3 → current = [1, 2, 3]. Call backtrack(3, [1, 2, 3]). Index = 3 = length → base case. Collect subset [1, 2, 3].

Step 5: Backtrack: remove 3 → current = [1, 2]. Exclude 3 → call backtrack(3, [1, 2]). Base case. Collect [1, 2].

Step 6: Backtrack to index 1: remove 2 → current = [1]. Exclude 2 → call backtrack(2, [1]).

Step 7: Include 3 → current = [1, 3]. Call backtrack(3, [1, 3]). Base case. Collect [1, 3].

Step 8: Backtrack: remove 3. Exclude 3 → call backtrack(3, [1]). Base case. Collect [1].

Step 9: Backtrack to root: remove 1 → current = []. Exclude 1 → call backtrack(1, []).

Step 10: Include 2 → current = [2]. Call backtrack(2, [2]).

Step 11: Include 3 → current = [2, 3]. Backtrack(3, [2, 3]). Collect [2, 3].

Step 12: Exclude 3 → backtrack(3, [2]). Collect [2].

Step 13: Backtrack: exclude 2 → current = []. Call backtrack(2, []).

Step 14: Include 3 → current = [3]. Collect [3].

Step 15: Exclude 3 → current = []. Collect [].

Step 16: All 8 subsets collected: [[1,2,3], [1,2], [1,3], [1], [2,3], [2], [3], []].

Backtracking Decision Tree — Include or Exclude Each Element — Watch how the recursion explores both include and exclude branches for each element, building a binary decision tree that produces all 2ⁿ subsets.

Algorithm

  1. Create an empty result list and an empty current subset
  2. Define a recursive function backtrack(index, current):
    a. Base case: If index == nums.length, add a copy of current to the result and return
    b. Include branch: Append nums[index] to current, then call backtrack(index + 1, current)
    c. Exclude branch: Remove the last element from current (backtrack), then call backtrack(index + 1, current)
  3. Call backtrack(0, []) to start the recursion
  4. Return the result list

Code

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> current;
        backtrack(nums, 0, current, result);
        return result;
    }
    
    void backtrack(vector<int>& nums, int index,
                   vector<int>& current,
                   vector<vector<int>>& result) {
        // Base case: processed all elements
        if (index == nums.size()) {
            result.push_back(current);
            return;
        }
        
        // Include nums[index]
        current.push_back(nums[index]);
        backtrack(nums, index + 1, current, result);
        
        // Exclude nums[index] (backtrack)
        current.pop_back();
        backtrack(nums, index + 1, current, result);
    }
};
class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        result = []
        
        def backtrack(index: int, current: list[int]):
            # Base case: processed all elements
            if index == len(nums):
                result.append(current[:])
                return
            
            # Include nums[index]
            current.append(nums[index])
            backtrack(index + 1, current)
            
            # Exclude nums[index] (backtrack)
            current.pop()
            backtrack(index + 1, current)
        
        backtrack(0, [])
        return result
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrack(int[] nums, int index,
                           List<Integer> current,
                           List<List<Integer>> result) {
        // Base case: processed all elements
        if (index == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        // Include nums[index]
        current.add(nums[index]);
        backtrack(nums, index + 1, current, result);
        
        // Exclude nums[index] (backtrack)
        current.remove(current.size() - 1);
        backtrack(nums, index + 1, current, result);
    }
}

Complexity Analysis

Time Complexity: O(n × 2ⁿ)

The recursion tree has 2ⁿ leaves (one per subset). Each leaf triggers a copy of the current subset into the result, which takes up to O(n) time. Internal nodes contribute O(1) work each (a push and a pop). Total: O(n × 2ⁿ) for the copies plus O(2ⁿ) for the traversal.

Space Complexity: O(n) auxiliary

The recursion stack has depth n (one frame per element). The current vector holds at most n elements. Together, auxiliary space is O(n). The output itself is O(n × 2ⁿ), but that is inherent to the problem (all subsets must be stored). Compared to the iterative approach, backtracking avoids intermediate cloning — it builds each subset incrementally and copies only at the leaves.