78. Subsets

Problem Statement in English

You’re given an array. Your task is to return the powerset of that array, i.e., every possible subset of that array.

Approach

Modelling this as a decision tree makes it so much simpler. Think about it. Say you’re given an array, [1,2,3,4,5], and you want to find every subset. Let’s work through it by hand:

• We can start at index 0 - we’ve 2 options, either include, or exclude it. This generates 2 possibilities. Let’s build our next solution on each of these 2 options.
• In both of those 2 options we can either include, or exclude index 1. Since we have 2 options per solution, that’s $2*2=4$ generated arrays.
• We continue this process until we’ve exhausted all indices in the original array that we can either include, or exclude.

Here’s what the decision tree would look like for the array [1,2,3]

    graph TD
    A(<>) -->|don't pick 1| B(<>)
    A -->|pick 1| C(<1>)

    B -->|don't pick 2| D(<>)
    B -->|pick 2| E(<2>)

    C -->|don't pick 2| F(<1>)
    C -->|pick 2| G(<1,2>)

    D -->|don't pick 3| H(<>)
    D -->|pick 3| I(<3>)

    E -->|don't pick 3| J(<2>)
    E -->|pick 3| K(<2,3>)
    
    F -->|don't pick 3| L(<1>)
    F -->|pick 3| M(<1,3>)
    
    G -->|don't pick 3| N(<1,2>)
    G -->|pick 3| O(<1,2,3>)

As you can see, the leaf nodes contain all the subsets. It’s important to note that this approach doesn’t generate duplicates when the array has distinct elements.

Solution in Python

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:

        # we'll store all unique possbilities in this
        ans = []
        
        # i'm using this to have access to the `ans` variable without having to pass it around
        def recursiveCall(l :List, i:int):
            # reached leaf node status
            if i == len(nums)-1:
                # create a copy of the previous result,
                #  and append the value at this index to it
                yes = l.copy()
                yes.append(nums[i])

                # copy the previous result
                no = l.copy()

                # since we've reached the leaf node, 
                # we don't need to perform any further appends,
                # and this forms part of our asnwer.
                # So we save both options
                ans.append(yes)
                ans.append(no)
            # we've gone out of bounds
            # let go of this path
            elif i > len(nums):
                pass
            # not a leaf node, and further indices to include or exclude exist
            else:
                yes = l.copy()
                yes.append(nums[i])
                # pass this possibility into the recursive call
                # to form the base of subsequent answers
                recursiveCall(yes, i+1)

                # pass this possibility into the recursive call
                # to form the base of subsequent answers
                recursiveCall(l.copy(), i+1)
        
        # initial call
        recursiveCall([], 0)

        # our final answer
        return ans

Complexity

• Time: $O(n \times{2^n})$
  This is because we generate $2^n$ possibilities per choice, and since we have $n$ choices, that’s $n*2^n$.

• Space: $O(n \times 2^n)$
  This is because our final answer list contains $2^n$ possible answers, with each answer containing $n$ elements at most. Hence $n \times 2^n$.

Mistakes I Made

The usual fumbling whilst building a recursive solution. It all came together once I could put my finger on the base case.

And we are done.