looping through loops in python?

Question

I'm trying to solve this problem on the easy section of coderbyte and the prompt is:

Have the function ArrayAdditionI(arr) take the array of numbers stored in arr and return the string true if any combination of numbers in the array can be added up to equal the largest number in the array, otherwise return the string false. For example: if arr contains [4, 6, 23, 10, 1, 3] the output should return true because 4 + 6 + 10 + 3 = 23. The array will not be empty, will not contain all the same elements, and may contain negative numbers.

Here's my solution.

def ArrayAddition(arr):
arr = sorted(arr, reverse=True)
large = arr.pop(0)
storage = 0
placeholder = 0
for r in range(len(arr)):
    for n in arr:
        if n + storage == large: return True
        elif n + storage < large: storage += n
        else: continue
    storage = 0
    if placeholder == 0: placeholder = arr.pop(0)
    else: arr.append(placeholder); placeholder = arr.pop(0)
return False

print ArrayAddition([2,95,96,97,98,99,100])

I'm not even sure if this is correct, but it seems to cover all the numbers I plug in. I'm wondering if there is a better way to solve this through algorithm which I know nothing of. I'm thinking a for within a for within a for, etc loop would do the trick, but I don't know how to do that.

What I have in mind is accomplishing this with A+B, A+C, A+D ... A+B+C ... A+B+C+D+E

e.g)

for i in range(len(arr):
print "III: III{}III".format(i)
storage = []
for j in range(len(arr):
    print "JJ: II({}),JJ({})".format(i,j)

    for k in range(len(arr):
        print "K: I{}, J{}, K{}".format(i,j,k)

I've searched all over and found the suggestion of itertool, but I'm wondering if there is a way to write this code up more raw.

Thanks.

Answer 1

A recursive solution:

def GetSum(n, arr):
    if len(arr) == 0 and n != 0:
        return False
    return (n == 0 or  
      GetSum(n, arr[1:]) or  
      GetSum(n-arr[0], arr[1:]))

def ArrayAddition(arr):
    arrs = sorted(arr)
    return GetSum(arrs[-1], arrs[:-1])

print ArrayAddition([2,95,96,97,98,99,100])

The GetSum function returns False when the required sum is non-zero and there are no items in the array. Then it checks for 3 cases:

1. If the required sum, n, is zero then the goal is achieved.
2. If we can get the sum with the remaining items after the first item is removed, then the goal is achieved.
3. If we can get the required sum minus the first element of the list on the rest of the list the goal is achieved.