Submission #5429881

---

Source Code Expand

def canMake(num, val):
    if memo[num][val] != -1:
        if memo[num][val] == 1:
            return 1
        else:
            return 0
    if num == 0:
        if val == 0:
            return True
        return 0
    if val - p[num-1] < 0:
        if canMake(num-1, val):
            memo[num][val] = 1
            return 1
        else:
            memo[num][val] = 0
            return 0
    else:
        if canMake(num-1, val-p[num-1]) or canMake(num-1, val):
            memo[num][val] = 1
            return 1
        else:
            memo[num][val] = 0
            return 0

n = int(input())
p = list(map(int, input().split()))

memo = [[-1] * (sum(p)+1) for _ in range(n+1)]

count = 0
for i in range(sum(p)+1):
    if canMake(n, i):
        count += 1

print(count)

Submission Info

Judge Result