Recursion solution not working for Subsets II from Leetcode-CodePudding

Can someone please help me find the bug in the below code for the problem statement on Leetcode : Subsets II (https://leetcode.com/problems/subsets-ii/)

class Solution:
    def func(self, ind, arr, ds, ans):
        ans.append(ds)
        
        for i in range(ind, len(arr)):
            if(i != ind and arr[i] == arr[i - 1]):
                continue
                
            ds.append(arr[i])
            self.func(i   1, arr, ds, ans)
            ds.pop()
    
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        sets = []
        
        nums.sort()
        self.func(0, nums, [], sets)
        
        return sets

On completion, the resultset - sets returns an empty list instead of the below expected output for the given sample case:

Input: [1,2,2]

Expected Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

CodePudding user response：

The problem with your code is that you're only ever adding references to the same ds list to your ans list. Because the contents of ds changes as you go through your algorithm, it has a solution in it when you append it each time, but when the algorithm ends, ds is empty. That's why you get list with several empty lists in it if you look at your output:

>>> s = Solution()

>>> s.subsetsWithDup([1,2,2])
[[], [], [], [], [], []]

There's a simple fix for this problem. Rather than appending ds itself to your results, append a shallow copy of it. Then the copy won't change when you modify ds later on.

def func(self, ind, arr, ds, ans):
    ans.append(list(ds))              # make a copy of ds here, by calling list!

    ... # the rest of the code is fine

CodePudding user response：

The problem states that order doesn't matter, yet you sort the list of numbers. You're trying to solve it recursively, yet there's an iterative loop as the main body of your code.

As @Blckknght points out ( 1), you fail to copy an item you try to save, so you always get multiple pointers to its final value. Adding that fix to your code, tossing the sorting, and replacing your variable names, we get something like:

class Solution:
    def subsetsWithDup_recursive(self, index, numbers, stack, answer):
        answer.append(list(stack))

        for i in range(index, len(numbers)):
            if i != index and numbers[i] == numbers[i - 1]:
                continue

            stack.append(numbers[i])
            self.subsetsWithDup_recursive(i   1, numbers, stack, answer)
            stack.pop()

    def subsetsWithDup(self, numbers):
        answer = []

        self.subsetsWithDup_recursive(0, numbers, [], answer)

        return answer

answer = Solution()

print(answer.subsetsWithDup([1, 2, 2]))

OUTPUT

> python3 test.py
[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
>