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]]:
        res = []
        N = len(nums)

        def dfs(i, curr):
            if i >= N:
                res.append(curr.copy())
                return

            curr.append(nums[i])
            dfs(i + 1, curr)
            curr.pop()

            dfs(i + 1, curr)

        dfs(0, [])

        return res

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$.

And we are done.