Python3.6，在递归回溯期间尝试附加到属性列表，但它丢弃结果吗？

Question

我正在尝试使用递归回溯生成所有唯一子集。 （面试准备）。问题陈述是：给定一组不同的整数nums，返回所有可能的子集（幂集）。注意：解决方案集不得包含重复的子集。

尽管，对于输入[1,2,3]，我的输出是：

[[],[],[1],[1,2],[1],[],[2],[]]

当答案应该是：

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

但是，当我打印出要添加到列表中的内容时，它会打印出正确的答案：

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

我认为递归地传递这些列表，重用它们等等可能是个问题，所以我制作了参数的副本。由于某种原因，我也必须对参数运行一个副本。

我是否缺少对这些数据结构的内存管理的了解？采用这种方法处理其他回溯问题时，我遇到了同样的问题。

class Solution:
    def __init__(self):
        self.subset = [[]]

    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.initSubsets(nums,[])
        return self.subset

    def initSubsets(self,options,currentSubset):
        frameOptions = options.copy()
        frameCurrentSubset = currentSubset.copy()

        for option in options:
            # add option to subset
            frameCurrentSubset.append(option)
            # add to solution
            self.subset.append(frameCurrentSubset)
            print(frameCurrentSubset)
            # guarentee no dups
            frameOptions.remove(option)
            # recurse
            self.initSubsets(frameOptions,frameCurrentSubset)
            # undo changes
            frameCurrentSubset.remove(option)

        return

Answer 1

我认为您的问题出在这一行：

self.subset.append(frameCurrentSubset)

您将列表追加到列表的位置，但以后您使用的位置

frameCurrentSubset.remove(option)

从frameCurrentSubset中删除元素的位置。但是问题是这样做的话，您还从复制到self.subset的列表中删除了该元素，因为它与内存中的列表相同。

解决方案是改用：

self.subset.append(frameCurrentSubset[:])

将添加一个新列表，该列表包含当时frameCurrentSubset的所有元素。

完整的解决方案是：

from typing import List

class Solution:
    def __init__(self):
        self.subset = [[]]

    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.initSubsets(nums,[])
        return self.subset

    def initSubsets(self,options,currentSubset):
        frameOptions = options.copy()
        frameCurrentSubset = currentSubset.copy()

        for option in options:
            # add option to subset
            frameCurrentSubset.append(option)
            # add to solution
            self.subset.append(frameCurrentSubset[:])
            print(frameCurrentSubset)
            # guarentee no dups
            frameOptions.remove(option)
            # recurse
            self.initSubsets(frameOptions,frameCurrentSubset)
            # undo changes
            frameCurrentSubset.remove(option)

        return

example = Solution()
result = example.subsets([1, 2, 3])
print(result)