Biểu thức cộng trừ đạt mục tiêu

General
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
recursion
Submissions
Đề bài

Cho dãy $N$ số nguyên $A_1, A_2, \dots, A_N$ và một số nguyên $S$. Với mỗi phần tử $A_i$ ($1 \le i \le N$), bạn phải gán một trong hai dấu + hoặc - vào trước $A_i$. Hãy viết hàm đệ quy đếm số cách gán dấu sao cho tổng của biểu thức thu được bằng đúng $S$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $S$.\nDòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$.

Dữ liệu ra

Một số nguyên duy nhất là số cách gán dấu thỏa mãn.

Ví dụ
Input Output
4 0\n1 1 1 1 6
1 3\n3 1
Giới hạn

$1 \le N \le 15$, $0 \le A_i \le 100$, $-2000 \le S \le 2000$.

Draft saved