CODEWITHSUNDEEP
pythonbacktracking
Victor Cui
Victor Cui

Reputation: 1705

Leetcode 78: Subsets confused why duplicate subsets are generated

I'm working on Leetcode 78: subsets and I've copied over the question below.

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.

I have a solution that generates some of the subsets, but not all of them. It also includes duplicate subsets.

def subsets(self, nums: List[int]) -> List[List[int]]:
        subsets = []
        expected_subsets = 2**len(nums)
        def generate_subset(subset, nums):
            # base case , gone too far
            if len(subsets) >= expected_subsets:
                return
            if len(subsets) < expected_subsets:
                subsets.append(subset)
            for i in range(len(nums)):
                # choose the current element
                generate_subset(subset+[nums[i]], nums[i+1:])
                # don't choose the current element
                generate_subset(subset, nums[i+1:])
        generate_subset([], nums)
        return subsets

My thinking is that for generating subsets, at each choice (number from nums) we have two options. We can either choose the current number (nums[i]) and generate the subset from the rest of the array, or we can skip the current number (nums[i]) and generate the subset from the rest of the array. But for the input nums = [1,2,3], my code generates [[],[1],[1,2],[1,2,3],[1,2],[1],[1,3],[1]] where the expected output is [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]. So I have some duplicate subsets. I'm unsure why [2] and [3] are not being generated. For reference, I have solved Leetcode 46: Permutations previously and I probably had my solution for that in mind (copied below) when I was solving subsets.

def permute(self, nums: List[int]) -> List[List[int]]:
        results = []
        n = len(nums)
        def dfs(permutation, nums):
            if len(permutation) == n:
                results.append(copy.deepcopy(permutation))
                return
            for i in range(len(nums)):
                permutation.append(nums[i])
                dfs(permutation, nums[:i] + nums[i+1:])
                # backtracking
                permutation.pop()
        dfs([], nums)
        return results

Can anyone explain why by subset code generates duplicate subsets? The issue of duplicate subsets is related to why I'm not generating the complete list of subsets.

Upvotes: 1

Views: 947

Answers (2)

funnydman
funnydman

Reputation: 11366

No need to have the second recursive call, the working solution is:

def subsets(nums: List[int]) -> List[List[int]]:
    subsets = []
    expected_subsets = 2 ** len(nums)

    def generate_subset(subset, nums):
        # base case , gone too far
        if len(subsets) >= expected_subsets:
            return
        if len(subsets) < expected_subsets:
            subsets.append(subset)
        for i in range(len(nums)):
            generate_subset(subset + [nums[i]], nums[i+1:])

    generate_subset([], nums)
    return subsets


print(subsets([1, 2, 3]))

# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Try to manually go through recursion calls and you understand why the previous version didn't work, took me a while. On that recursive call, you get current and recursively process the rest.

This is an example of explicit pick/don't pick approach:

def subsets(nums: List[int]) -> List[List[int]]:
    result = []

    def powerset(alist, index, curr):
        if index == len(alist):
            result.append(curr)
            return

        powerset(alist, index + 1, curr + [alist[index]])  
        powerset(alist, index + 1, curr)

    powerset(nums, 0, [])
    return result

Upvotes: 1

Yonas
Yonas

Reputation: 141

Similar but alternative solution.

def subsets(nums):
    power_set = []
    subset = []
    nums_len = len(nums)

    def find_subsets(start):
        power_set.append(subset.copy())

        for i in range(start, nums_len):
            subset.append(nums[i])
            find_subsets(i + 1)
            subset.pop()

    find_subsets(0)
    return power_set

Upvotes: 1

Related Questions