Recursive backtracking in Python -- balancing weights on a scale

Question

Problem: Suppose you have a weight on one side of a scale. Given an array of other weights, see if the scale will balance. You can use weights on either side, and you don't have to use all the weights.

In my current solution, I have 3 branches at each level. The first adds the first weight in the array to the "left" side, the second simply discards it, and the third adds it to the "right" side. My issue seems to be that that after completing the first branch, it returns False if all of the branches come out to be False. Instead, I want it to move on to the next branch.

What tipped me off to this is that when I have weights = [4,1] and init_weight = 3, it gives me the wrong message (saying that it can't be balanced), but when I flip the order of weights to be [1,4], it gives me the correct message.

I just started learning Python yesterday, so my guess is that I'm missing some sort of syntactic subtlety. But that definitely doesn't rule out algorithmic issues!

def balanceable_rec(L, R, weights):

    print("L =", L, "  R =", R, "  weights =", weights)

    if (L == 0  or  L==R  or L in weights):
        return True
    if (len(weights) == 0):
        return False

    w = weights.pop(0)
    if balanceable_rec(L + w, R, weights):  return True
    if balanceable_rec(L, R, weights):      return True
    if balanceable_rec(L, R + w, weights):  return True

    return False


def balanceable(w, weights):
    return balanceable_rec(w, 0, weights)


# ----------------------

# weights = [1,4]
weights = [4,1]
init_weight = 3

if (balanceable(init_weight, weights)):     print("That can be balanced!")
else:           print("That cannot be balanced!")

Here's the output:

L = 3 R = 0 weights = [4, 1]

L = 7 R = 0 weights = [1]

L = 8 R = 0 weights = []

L = 7 R = 0 weights = []

L = 7 R = 1 weights = []

L = 3 R = 0 weights = []

L = 3 R = 4 weights = []

That cannot be balanced!

score 3 · Accepted Answer · answered Mar 20 '14 at 08:48

3

You need to pass copies of weights to your recursive calls, so that the pop call doesn't affect the original weights object, e.g.:

def balanceable_rec(L, R, weights):

    print("L =", L, "  R =", R, "  weights =", weights)

    if (L == 0  or  L==R  or L in weights):
        return True
    if (len(weights) == 0):
        return False

    w = weights.pop(0)
    if balanceable_rec(L + w, R, weights[:]):  return True
    if balanceable_rec(L, R, weights[:]):      return True
    if balanceable_rec(L, R + w, weights[:]):  return True

    return False

answered Mar 20 '14 at 08:48

Marius

58,213
16
107
105

Thank you, that fixed my problem. So the lesson here is that Python by default passes things by reference, not by copy? – devonzuegel Mar 20 '14 at 18:05
@shortcake56: That's basically the problem you were having, although I think technically Python doesn't do pass by reference but something slightly different, see [here](http://stackoverflow.com/questions/986006/python-how-do-i-pass-a-variable-by-reference) – Marius Mar 21 '14 at 03:13

Recursive backtracking in Python -- balancing weights on a scale

1 Answers1