0

Edit: I know this question has been asked a million times, but I can't seem to find anything that works for my specific scenario. For context purposes, I'm running Python 3.6 on a Windows OS.

I've tried the following code:

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target:
        print(f"sum({partial})={target}")
        #print("sum({})={}".format(partial, target))
    if s == target:
        return  # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        #remaining = numbers[:i] + numbers[i+1:]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n])

s= [-765143.910000006, -14522903.45, -185360.52, -161161.559999994, -31947.78, 167450, 47715.46, -1725.24, -1532.91, 338381.23, -40962.19, -321.869999999997, -28215.17, -66345.71, 13063.28, -389.37, 6215992.30000001, 2193804.53000001, -458374.52, 106792.609999979, -335194.01, 203687.94, 91147.0500000003, -18.9500000000004, -19.1200000000016, -2.31494823310641]

k= [-2191.62999999806, 5481451.91, -17941.98, 166.719999999996, -2.72848410531878, -3.42659234320308, -13109322.84, -5320290.35000001, -977974.9, 2224562.69999999, 404360.300000002, 579934.88, 1131275.75, 3889264.3, 3364573.99000001, 5225874.59, 2191.62999999806, 176248.27, 19925.25, 2090.84, 11461.32, 3457.83, 4655.76, -17929.46, 449.48, 2187.61, 3084.35, 176274, 48909.78, 55.43]

x= [14795.41, 6497.05, 324.6, 5589.19, 2224.45, 5571.92, 3575.24, 3041.33, 4658.22, 6244.92, 433.59, 2146.55, 1489, 28686.93, 205, 2267.76, 1532.91, -12539.19, 46221.03, 9959.25, 20175.14, 735, 9449, 26880, 426.12, 1355.18, 220.48, 695.88, -389.99, -1.12, -37.56]

v= [-1.96999999999248, 1.58761892521397, -2.1600499167107, -2791.41999999999, 606814.85, -19.1200000000016, -1.49999999999995, -54.3300000000086, 34608.19, -661601.97, 3149949.45, 32247.78, 350.64, 328574.84, 42461.52, 1273, 6635.21, 504, -3100.27, 9868.07, 148179.28, 29205.46, -206.65, -552]

y = [s+k+x+v]

if __name__ == "__main__":
    subset_sum(y, -765143.910000006)
KevinA626
  • 3
  • 3

4 Answers4

2

This line

print(sum(%s)=%s) % (partial, target)

is wrong because you are using patterns of string formatting for things that are not strings. You probably wanted to do

print("sum(%s)=%s" % (partial, target))

and still this is old syntax, you'd prefer the new syntax

print("sum({})={}".format(partial, target))
JulienD
  • 7,102
  • 9
  • 50
  • 84
  • 1
    And since the OP is using Python 3.6, they can make it even more modern & more compact (and faster), using an f-string: `print(f"sum({partial})={target}")` – PM 2Ring Oct 24 '17 at 19:34
  • Oh, nice, I did not know that! – JulienD Oct 24 '17 at 19:35
  • Thanks, guys - it worked! I do have a follow up question, though: it seems when I try including negative numbers in the set, the script fails. How would I be able to include negative numbers in the set to also be tested in combination with positive and/or negative numbers also in the set to equal a certain sum? For example, if I have (10, -5, -9, 8, -2) and I want the combinations that equal 5, one of the solutions would be 10, -5. Thank you! – KevinA626 Oct 24 '17 at 19:51
  • Shouldn't `remaining` be instead `numbers[:i] + numbers[i+1:]` ? It seems to me that you are missing combinations. Also `partial` could be just an int, you don't need to concatenate to a list, just accumulate the result of the sum. – JulienD Oct 24 '17 at 20:02
  • The end condition (`if s >= target`) is also not suiting well as a condition to reach a negative target. In particular, the first sum (of `partial = []`, so 0), will terminate your algorithm with any negative target. – JulienD Oct 24 '17 at 20:12
  • Edit your question instead of posting code in comments, please. Mark it with an **Edit:** before it. – JulienD Oct 24 '17 at 21:18
  • Ahh, didn't know you could do that. Added code to question. – KevinA626 Oct 24 '17 at 21:23
0

Concerning SyntaxError: you used formatting in incorrect way. More on that on PyFormat site, just quick solution:

print("sum(%s) =%s" % (partial, target))
olhur
  • 125
  • 1
  • 9
0

Your code doesn't work because 

print(sum(%s)=%s) % (partial, target)

Should be

print "sum(%s)=%s" %(partial, target)

Furthermore you need to indent the line after your main declaration

if __name__ == "__main__":
subset_sum([3,9,8,4,5,7,10],15)

Should be this

if __name__ == "__main__":
  subset_sum([3,9,8,4,5,7,10],15)

Also your code does not work completely as subset_sum([3,9,8,4,5,7,10,-9],1) does not return a result even though it should return [10,-9]=1.

Furthermore, to improve on your code I'd recommend using memoization to avoid having to calculate the same subset more than once if you are doing this over large sets of numbers.

Ranger
  • 1
  • 3
  • Hi Ranger, Thanks for the input! Do you know what changes I could make to make the script work with negative numbers as well (like the example you provided above)? – KevinA626 Oct 24 '17 at 19:59
  • It looks like your logic is working now. That being said you have to change y = [s+k+x+v] to y = s+k+x+v – Ranger Oct 26 '17 at 19:04
0

I believe this code works:

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)
    if len(numbers) == 0:
        return
    elif s == target:
        print("sum({})={}".format(partial, target))
        return
    else:
        for i in range(len(numbers)):
            n = numbers[i]
            remaining = numbers[:i] + numbers[i+1:]
            subset_sum(remaining, target, partial + [n])

y = [-15, 5, 10, -10, 3, 7, -4, -2]

if __name__ == "__main__":
    subset_sum(y, 6)

It can be extremely slow as the number of possible combinations increases, which you can count mathematically and grows astronomically, so you feel like it is never going to end.

N.B. I don't have Python 3.6 so the formatting will remain old-school here.

Edit: Another note is that you should never use equality between floats, like in your termination condition with the new input you propose. You can have a look at this answer for inspiration for a if isclose(s, target) condition.

JulienD
  • 7,102
  • 9
  • 50
  • 84
  • @KevinA626 You tried to edit my question to ask yours, SO does not work like that. Add a comment instead. Your mistake is `y = int[s+k+x+v]`, which has 2 errors: first `[s+k+x+v]` is a list of lists, not a list; second, this is not how you cast to int in Python. use `map(int, somelist)` instead, or `[int(x) for x in somelist]`. – JulienD Oct 25 '17 at 13:02
  • My apologies! New to this. – KevinA626 Oct 25 '17 at 15:58