타겟넘버

Description

n개의 음이 아닌 정수가 있다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수가 있다.

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

사용할 수 있는 n개의 숫자가 담긴 배열 numbers, 타겟 넘버 target이 입력이 될 때, 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 출력한다.

Input

첫째 줄은 주어지는 숫자의 개수 n (2 ≤ n ≤ 20)이다.

두번째 줄에는 배열 numbers의 원소(1이상 50이하인 자연수)들이 주어진다.

세번째 줄에는 타겟 넘버 traget(1≤ target ≤1000인 자연수)가 주어진다.

Output

숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 출력한다.

Sample Input 1 

5
1 1 1 1 1
3

Sample Output 1

5

def solution(numbers, target):
    data =[0]
    for num in numbers:
        res = []
        for val in data:
            res.append(val+num)
            res.append(val-num)
        data = res
    return data.count(target)



n = int(input()) #size of numbers
numbers = list(map(int, input().split()))
target= int(input())

cnt = solution(numbers, target)

print(cnt)