python - 如何检查数组中是否可以求和？

Question

Given an array of N integers, check if it is possible to obtain a sum of S, by choosing some (or none) elements of the array and adding them.

我尝试使用贪婪的方法解决这个问题，首先对数组进行排序，然后越来越接近总和。但是它不起作用。

谁能告诉我应该如何解决这个问题？

t = int(input())
for foo in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    s = int(input())
    sum = 0

    for a in range(len(arr)):
        for b in range(len(arr)-a-1):
            if(arr[b] > arr[b+1]):
                temp = arr[b]
                arr[b] = arr[b+1]
                arr[b+1] = temp

    for i in arr:
        if((sum + i) <= s):
            sum += i

    if(sum == s):
        print("YES")
    else:
        print("NO")

Answer 1

使用 itertools.combinations 的暴力(并且可以说非常慢)解决方案:

from itertools import combinations

def is_possible_sum(numbers, n):
    # One of those rare cases where range() is ok!
    for r in range(len(numbers)):
        for combo in combinations(numbers, r + 1):
            if sum(combo) == n:
                return True
    return False