在Python中循环循环？

Question

我试图在coderbyte的简单部分解决这个问题,提示是:

让函数ArrayAdditionI(arr)获取存储在arr中的数字数组,如果数组中的任何数字组合可以添加到数组中的最大数字,则返回字符串true,否则返回字符串false.例如:如果arr包含[4,6,23,10,1,3],则输出应返回true,因为4 + 6 + 10 + 3 = 23.数组不会为空,不包含所有相同的元素,并且可能包含负数.

这是我的解决方案.

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

我甚至不确定这是否正确,但它似乎涵盖了我插入的所有数字.我想知道是否有更好的方法通过我不知道的算法来解决这个问题.我正在考虑for for for for for,et循环可以解决问题,但我不知道如何做到这一点.

我的想法是用A + B,A + C,A + D ... A + B + C ...... A + B + C + D + E来实现这一目标

例如)

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)

我已经搜遍了所有的并发现了itertool的建议,但是我想知道是否有办法更加原始地编写这个代码.

谢谢.

Answer 1

递归解决方案：

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

当所需的总和非零并且数组中没有项目时，GetSum 函数返回 False。然后它检查 3 种情况：

1. 如果所需的总和 n 为零，则目标达到。
2. 如果去掉第一项后能与剩下的项求和，那么目的就达到了。
3. 如果我们能够得到所需的总和减去列表其余部分的第一个元素，则目标就达到了。