Biểu thức cộng trừ đạt mục tiêu
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
recursion
Đề 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$.
Community Discussion