使用 Python 和 class 的子集总和

Question

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

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

它应该生成一棵树。树得到一个数据列表和一个值。该值最初为 0。然后它填充它的 children。每个节点有2children。 children的数据都是parent的数据去掉了top值。但是 child 会将其添加到值中，而不会。

例如

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

树示例（深度到第 2 层）：

- 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 设置为对数据的引用，而不是副本。

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

解决此问题的两种方法：

方法一

改变

self.data = data

到

self.data = data[:]

这会为每个树节点复制一份数据。

方法二

添加行

self.data.append(top_val)

在填充调用结束时。

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

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

使用 Python 和 class 的子集总和

Sum of subsets using Python with class

python

algorithm

recursion

computer-science

方法一

方法二