递归解决方案不工作的子集II从Leetcode

Question

有人能帮我找到下面代码中的错误在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

完成后，resultset - sets返回一个空列表，而不是给定示例情况的以下预期输出:

输入:[1、2、2]

预期输出:[[],[1],[1,2],[1、2、2],[2],[2 2]]

Answer 1

您的代码的问题是，您只添加引用到相同的ds列表到您的ans列表。由于ds的内容随着算法的进行而变化，每次添加时，它中都有一个解，但当算法结束时，ds为空。这就是为什么您会得到一个包含几个空列表的列表，如果您查看您的输出:

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

这个问题有一个简单的修复方法。而不是将ds本身附加到您的结果中，而是附加它的浅副本。然后，当您修改ds时，副本将不会改变。

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

Answer 2

问题表明顺序无关紧要，但您对数字列表进行了排序。你试图递归地解决它，但你的代码主体是一个迭代循环。

正如@ blackknight指出的(+1)，你无法复制你试图保存的项目，所以你总是得到指向其最终值的多个指针。将这个修复添加到代码中，抛开排序，替换变量名，我们得到如下内容:

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

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