Problem Statement

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Additional information

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

Example 1:

Input: nums = [1, 2, 3]

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

Example 2:

Input: nums = [0]

Output: [[], [0]]

Iterative Cascading (Brute Force)

Intuition

The simplest way to generate all subsets is to build them up iteratively. We start with the most basic subset: an empty list [].
Then, we take the first number in our input array, and we add it to every subset we've generated so far. We take the second number, and add it to all the new and old subsets, doubling our total number of subsets. We cascade this process for every number in the input array until we have generated the entire power set.

Algorithm

1. Initialize a list of lists called res with an empty subset inside it: [[]].
2. Loop through every num in the nums array.
3. Inside the loop, iterate through all the existing subsets currently inside res.
4. For each existing subset, create a new subset by appending the current num to it.
5. Add all these newly formed subsets back into res.
6. Return res.

def subsets(nums: list[int]) -> list[list[int]]:
    res = [[]]
    
    for num in nums:
        # Create new subsets by adding 'num' to each existing subset
        new_subsets = [curr_subset + [num] for curr_subset in res]
        res.extend(new_subsets)
        
    return res

Time & Space Complexity

• Time complexity: O(N * 2^N)

• Reason: For an array of size N, there are exactly 2^N possible subsets. For each element N, we are iterating over all previously generated subsets and creating new ones. Creating a new array (copying elements) takes time proportional to its length. Thus, generating all 2^N subsets takes O(N * 2^N) time.

• Space complexity: O(N * 2^N)

• Reason: The res array must store all 2^N subsets, and the average length of each subset is N/2. Therefore, the memory consumed is strictly O(N * 2^N) to hold the output.

Recursive Backtracking / DFS - Optimal

Intuition

We can also formulate this as a classic "choose or don't choose" decision tree using Depth-First Search (DFS). At every step, we are looking at a specific number in the array. We have two branches:

1. Include the number in our current subset.
2. Don't include the number in our current subset.

By traversing every possible path in this decision tree, we naturally generate every unique subset. Backtracking is a very elegant way to represent this because we simply append a number, dive deeper into the recursion, and then pop() the number back out to explore the alternative path.

Algorithm

1. Initialize an empty list res to store the final subsets.
2. Create a recursive helper function dfs(i, current_subset) where i is our current index in the nums array.
3. Every time dfs is called, immediately append a copy of current_subset to res. (This captures all the intermediate states, including the empty list).
4. Start a for loop from i to the end of the nums array. Let the loop variable be j.
5. Inside the loop:

• Include: Append nums[j] to current_subset.
• Recurse: Call dfs(j + 1, current_subset) to explore paths including this number.
• Backtrack: Pop the last element from current_subset so the next iteration of the loop can try a different path.

6. Call dfs(0, []) to start the recursion.
7. Return res.

def subsets(nums: list[int]) -> list[list[int]]:
    res = []
    
    def dfs(i, current_subset):
        # Capture the current state of the subset
        res.append(current_subset.copy())
        
        # Explore adding subsequent numbers
        for j in range(i, len(nums)):
            current_subset.append(nums[j])
            dfs(j + 1, current_subset)
            
            # Backtrack to explore the path where we DON'T add nums[j]
            current_subset.pop()
            
    dfs(0, [])
    return res

Time & Space Complexity

• Time complexity: O(N * 2^N)

• Reason: There are 2^N total subsets. We are generating each one, and the operation current_subset.copy() takes O(N) time in the worst case.

• Space complexity: O(N)

• Reason: Excluding the output array, the auxiliary space used is entirely dictated by the recursion stack and the current_subset array. The deepest the recursion goes is the length of the array, so it takes O(N) space.