Problem Statement

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.

Examples

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

Constraints

• 1 <= nums.length <= 10

• -10 <= nums[i] <= 10

• All the numbers of nums are unique.

Intuition

This problem is a great fit for solving with recursion. Let's try to tackle it using the recursive framework we explored in The Recursive Journey blog:

• Identify actual problem: The actual problem here is to find all the possible subsets from a given array of numbers.

• Identify sub-problem: if we can form all the subsets for (n-1) numbers in the array, then we can form all the subsets for n numbers by either including it or excluding it from the curr_subset.

• Trust that the base function works: We have confidence in the function that computes all the subsets. It is designed to work effectively for all sub-problems and deliver the accurate solution.

• Link actual and sub-problem: Since we have found subset(n-1):

$$subset(n)=include\ or \ exclude \ n^{th}\ number$$

• Identify base case: Since we're moving from the 0th index of the nums array to the nth index, we cannot exceed the nth index. Therefore:

        if index==len(nums):
            res.append(curr_subset.copy())        
            return
  

  This will make sure recursive function does not go beyond the bounds of nums array.

Code Solution

Python Code:

# TC: O(2^n)
# SC: O(n+n)=> O(2n)=> O(n)
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        # initialize result array/list
        res=[]
        # call recursive function to form all subsets
        self.makeSubsets(0,[],nums,res)
        # return result
        return res
    def makeSubsets(self,index:int,curr_subset:List[int],nums:List[int],res:List[List[int]]):
        # base case
        # if index has reached end of array then
        #  we have no more numbers to form subsets
        # hence append curr_subset to res
        if index==len(nums):
            res.append(curr_subset.copy())
            return        
        # recursive case of including the current number in subset
        curr_subset.append(nums[index])
        self.makeSubsets(index+1,curr_subset,nums,res)        
        # recursive case of excluding the current number from subset
        curr_subset.pop()
        self.makeSubsets(index+1,curr_subset,nums,res)

Time and Space Complexity

Time Complexity:

$$O(2^n)$$

As for each recursive call we make two other recursive calls(one for including that number and one for excluding that number)

Space Complexity:

$$O(n+n)=>O(2n)=>O(n)$$

O(n) for the recursive stack and O(n) for the result array, which adds up to O(n+n). This simplifies to O(n).

Conclusion

As you can see 78. Subsets can be solved using recursion. In this problem we learn how at each recursive call we decide to include or exclude the number at current index in the curr_subset array/list.

I hope you got something useful from this blog post. If you've made it this far, please give it a like and drop your thoughts in the comments. Feel free to share any ideas for making future blog posts better.