Subsets

The problem description can be found in LeetCode.

Approach

As usual, the space tree is our friend:

At each step, we can either include the current element or exclude it (the x node). Lastly, it will be enough to append each solution we find in each leaf node to build up the expected result.

Solution

from typing import List


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def dfs(i: int, curr: List[int], subs: List[List[int]]) -> None:
            if i == len(nums):
                subs.append(curr.copy())
                return

            # include current element
            curr.append(nums[i])
            dfs(i + 1, curr, subs)
            curr.pop()

            # do not include current element
            dfs(i + 1, curr, subs)

        ans: List[List[int]] = []

        dfs(0, [], ans)
        return ans

Complexity

• Time: $O(2^n)$
• Space: $O(n)$

Where $n$ is the size of the nums list.