👯78. Subsets

Medium | Grind 75 | March 5th Sunday, 2023

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.

Constraints:

• 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]]

SOLUTION

This problem utilizes the backtracking technique, which involves exploring all possible solutions by incremental building and refining a "path" toward the solution. In this case, we iterate over each element in the given list, and for each element, we recursively build a path that includes the current element, as well as a path that excludes the current element. By doing so, we exhaustively generate all possible subsets of the input list. Refer to the diagram below to visualize the backtracking.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        def get_subset(nums:list, path:list, result:list): 
            if not nums: 
                return 
            
            for i in range(len(nums)): 
                path.append(nums[i])
                result.append(path[:])
                get_subset(nums[i+1:], path, result)
                path.pop()

            return result 

        
        return get_subset(nums, [], [[]])

TIME AND SPACE COMPLEXITY

TIME: O(2^n) where n is the length of the input list nums. This is because, for each element in the list, the function recursively generates two branches of the path - one that includes the element and another that excludes it. Since there are 2^n possible combinations of elements in a set of n elements, the function must generate and store all 2^n subsets.

SPACE: O(k*2^n) where n is the length of the input list nums and k is the average size of each subset. We generate 2^n subsets which on average have k elements in it.

**Written with help from ChatGPT