CSES - Meet in the middle

Xem PDF



Tác giả:
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, Perl, PHP, Prolog, Pypy 3, Python, Ruby, Rust, Scala, Swift
Điểm: 1500 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn được cho một mảng gồm \(n\) số. Có bao nhiêu cách chọn tập hợp con các số có tổng \(x\)?

Input

Dòng đầu tiên là hai số \(n\)\(x\) : kích thước mảng và tổng bắt buộc.

Dòng thứ hai chứa \(n\) số nguyên \(t_1,t_2,…, t_n\): các số trong mảng.

Output

In ra số cách bạn có thể tạo ra tổng \(x\).

Constraints

  • \(1 \le n \le 40\)
  • \(1 \le x \le 10^9\)
  • \(1 \le t_i \le 10^9\)

Example

Input

4 5
1 2 3 2

Output

3

Bình luận

Không có bình luận nào.