python - 使用Python与类的子集总和

Question

我正在尝试使用 Python 和递归来解决子集总和问题。子集总和问题应该找出一组数字中是否存在一个子集，其中该子集的总和等于目标值。我尝试了下面代码的多种变体。

据我所知，它总是停在最左边最深的分支处。

它应该生成一棵树。该树获取数据列表和值。该值一开始为0。然后它填充它的 child 。每个节点有 2 个子节点。两个 child 的数据都是 parent 的数据，去掉了最高的值。但只有一个 child 会将其添加到值(value)中，而另一个则不会。

例如

Set: (1, 4, 5, 3, 8)
Target: 4
Subsets: (1, 3), (4)

树示例(深度直到第二层):

- 0 (1, 4, 5, 3, 8)
-- 1 (4, 5, 3, 8)
---- 5 (5, 3, 8)
---- 1 (5, 3, 8)
-- 0 (4, 5, 3, 8)
---- 4 (5, 3, 8)
---- 0 (5, 3, 8)

class Tree:
    def __init__(self, value, data, target):
        self.value = value
        self.target = target
        self.data = data
        self.children = list()

        if self.value == target:
            print("Target found!")
            print(self.children)
            print(self.value)

        if len(self.data) != 0 and self.value < target:
            self.populate()

    def populate(self):
        top_val = self.data.pop()
        self.children.append(Tree(self.value + top_val, self.data, self.target))
        self.children.append(Tree(self.value, self.data, self.target))

    def print_children(self):
        print("value", self.value)
        for child in self.children:
            child.print_children()


if __name__ == "__main__":
    numbers = [3, 34, 4, 12, 5, 2]
    tree = Tree(0, numbers, 9)
    tree.print_children()

这是上面代码的输出:

value 0
value 2
value 7
value 19
value 7
value 11
value 7
value 41
value 7
value 10
value 7
value 2
value 0

Answer 1

问题在于 self.data 设置为对数据的引用，而不是副本。

这意味着所有 Tree 节点都指向完全相同的数据数组，因此当您调用 pop 时，这些值将从数据中永久删除。

解决此问题的两种方法:

方法1

改变

self.data = data

至

self.data = data[:]

这需要每个树节点的数据副本。

方法2

添加行

self.data.append(top_val)

在填充调用结束时。

这会将您弹出的值放回到数组中。

方法 2 使用较少的内存，但更容易出错，因为每个树对象仍然共享相同的数据数组。