Problem of The Day: Subsets

Similar to the Permutations problem on my other post, this problem involved in the backtrack topic. The interesting thing about this problem is that there are different ways to solve it. Personally, I figured out two approaches to solve this and I would present my thought process in this post.

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

My Explanation

Backtrack Approach

By applying the backtrack, we can explore the search space for this problem. The algorithm is very similar to the Permutations problem with a few minor changes. Instead of adding the solution at the leaf node of the recursive tree, we would like to append the subset at each node. In other words, when we traverse the search space in a recursive manner, we want to add the current solution or subset to our final solution array. Then, we use backtrack to revert the current state to the previous state to explore a different branch of the recursive tree.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(result, curr):
            result.append(curr[:])
            for num in nums:
                if num not in curr:
                    curr.append(num)
                    if sorted(curr) not in result:
                        backtrack(result, sorted(curr))
                    curr.pop()


        result = []
        backtrack(result, [])
        return result

Expanding Previous Candidate Approach

The second approach involves generating new solutions based on the previous candidate. The basic idea is to start with an empty array and generate different subsets by concatenating the empty list with each element in the input list.

For example, say we have an input array [1, 2, 3]. At the start, we always have an empty list no matter what.

result = []

Then, we create the subset by constructing the new subset or list with the first element. We will get the following.

[] -> [1] (new)
result = [], [1]

After that, we move on to the next element and use the previous result as the start point in stead of the empty list. We would get the following result.

# start with this
result = [], [1]

# for each item in the result, we add 2 to them
[]  -> [2]    (new)
[1] -> [1, 2] (new)

result = [], [1], [2], [1, 2]

Doing the same thing for the last number which is 3, we would get the final output.

[]     -> [3]       (new)
[1]    -> [1, 3]    (new)
[2]    -> [2, 3]    (new)
[1, 2] -> [1, 2, 3] (new)

result = [], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]

And this is my solution code this approach.

class Solution:
    def subsets(nums: List[int]) -> List[List[int]]:
        output = [[]]
        for num in nums:
            curr = []
            for x in output:
                curr.append(x[:])
            for i in range(len(curr)):
                curr[i].append(num)
            for x in curr:
                output.append(x[:])
        return output