Subsets | Leetcode 78

Welcome to our deep dive on Subsets (Leetcode 78). This is the foundational problem for understanding how to generate all branches of a decision tree.

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.

Example: nums = [1,2,3] => Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Approach: Cascading Recursive Backtracking O(N * 2^N)

Generating a Powerset implies that for every single element in the nums array, we have exactly two binary decisions:

1. We include it in our current subset.
2. We exclude it from our current subset.

We can use DFS to explore all these branches.

1. Create a dfs(i, current_subset) function.
2. Right away, append a copy of current_subset to our global result list. This captures the empty set, the full set, and everything in between.
3. Loop j from i up to the length of nums.
4. Include nums[j] in our current_subset.
5. Recurse by calling dfs for the next element: dfs(j + 1, current_subset).
6. Backtrack by popping nums[j] from current_subset.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        
        def dfs(i, current_subset):
            # Record the current combination
            res.append(current_subset[:])
            
            # Loop through decisions for remaining elements
            for j in range(i, len(nums)):
                current_subset.append(nums[j])
                dfs(j + 1, current_subset)
                current_subset.pop()
                
        dfs(0, [])
        return res

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (78)