Day 87 | Subsets II

A couple days ago, I solved a problem called subsets. Today I solved a problem that built off that last problem. The two problems are extremely similar with only one difference: the input array can now include duplicates. What makes this problem a little more difficult is the fact that the solution must not contain duplicate subsets.

The Approach

If the solution from the first problem is used, duplicate subsets would exist in the output array and here is why.

Ex: [1,2,2,3]

With the backtracking method that was used earlier, you essentially pick to include or not include each number in the list. So you start with one, you create a subset that includes the one and doesn't. Then with the one, you create a subset that includes the 2 and another that doesn't. You do that again with the next two to end up with [1,2,2] and [1,2] for including and not including the second two. The problem arises once you backtrack to the subset that includes the one but not the first two. You would now choose to either include or not include the second two to that subset to end up with [1] and [1,2]. The [1,2] is now a duplicate subset which is a problem.

The way we can counteract this issue is that if we choose to not include a number in a particular subset, we must make sure that it is never included again in it's children. So with the earlier example, we have the subset which is [1]. We now create two new subsets that either include or doesn't include the first two. So we end up with [1] and [1,2]. Now for [1], we want to make sure we skip the second two and go on to create new subsets that either include or not include the three.

The Code

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        def backtrack(i,subset):
            if i == len(nums):
                res.append(subset[::])
                return
            subset.append(nums[i])
            backtrack(i+1, subset)
            subset.pop()
            while i + 1 < len(nums) and nums[i] == nums[i+1]:
                i += 1
            backtrack(i+1, subset)
        backtrack(0, [])
        return res
                    

This solution is almost the same as the solution for the first problem. The only difference here is the while loop that skips the consecutive same numbers to make sure we don't create duplicate subsets. The solution also starts out with sorting the input array so it's in a form that works for this solution.

Complexity Analysis

The time complexity of this solution is O(2^n). The reason why this is the case is that for each number, we are either including the number or not including it. This means that the backtrack method is going to be called 2^n times.

The space complexity of this solution is also going to be O(2^n) again because the response is going to include 2^n elements as again we are either choosing to include or not include a specific number.