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

Question

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

不过，对于输入 [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)

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

Python3.6, trying to append to a attribute list during recursive backtracking, but it discards results?

recursion

backtracking

python-3.x