Leetcode 78. Subsets

Problem

Leetcode 78 - Subsets

Example:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Input: nums = [0]
Output: [[],[0]]

Approach

We can use DFS to solve this problem. More in depth representation is in visualization of the Approach

We can either add the element to subset or not add element.

Visualization of the Approach:

Input: nums = [1,2,3]

                    1 2 3
                /           \
            [1]                []
        /       \           /      \
    [1,2]        [1]       [2]       []
    /   \       /   \      /  \     /   \
[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3]   []

All the elements in the deepest are the subsets

Here is the Python code for the solution:

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

        def dfs(i, arr):
            if i == len(nums):
                res.append(arr)
                return
            
            dfs(i+1, arr)
            dfs(i+1, arr+[nums[i]])

        dfs(0, [])
        return res    

Time Complexity and Space Complexity

Time Complexity: $O(2^n)$

Space Complexity: $O(n)$