Sum of subsets using Python with class

Question

I'm trying to solve the sum of subset problem using Python and recursion. The sum of subsets problem is supposed to find if there exists a subset of a set of numbers where the sum of the subset is equal to a target value. I've tried many variations of the code below.

It always stops at the left most deepest branch as far as I can tell.

It is supposed to generate a tree. The tree gets a list of data and a value. The value is 0 at first. It then populates its children. Each node has 2 children. Both children's data is the parent's data with the top value taken off. But the one child will get it added to the value, and one won't.

e.g.

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

Tree example (depth till 2nd level):

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

This is the output of the code above:

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

*"Any and all help is appreciated."* Stack Overflow is for specific questions about programming; it's not clear what you are asking for other than general help. If your code works, please say so in the question and ask something specific about it; if it doesn't work, please provide an input, expected result and actual result. — kaya3, Nov 28 '19 at 18:53
can this previous question offer up some insights? checked it out? https://stackoverflow.com/questions/23087820/python-subset-sum — Gideon Maina, Nov 28 '19 at 19:18

score 2 · Accepted Answer · answered Nov 28 '19 at 22:00

The problem is that self.data is set to a reference to data, and not a copy.

This means that all Tree nodes point to the exact same data array, and that therefore when you call pop, the values are permanently removed from the data.

Two methods to fix this:

Method 1

Change

self.data = data

to

self.data = data[:]

this takes a copy of data for each Tree node.

Method 2

Add the line

self.data.append(top_val)

at the end of the populate call.

This will put the value you popped back into the array.

Method 2 uses less memory, but is more error prone because every tree object still shares the same data array.

Sum of subsets using Python with class

1 Answers1

Method 1

Method 2