Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Bài toán gốc trên GeeksforGeeks (viết hàm) được chuyển sang dạng nhập/xuất chuẩn (stdin/stdout).

Cho một mảng arr[] gồm các số nguyên không âm và một số nguyên sum, nhiệm vụ là đếm tất cả các tập con của mảng đã cho có tổng bằng sum cho trước.

Lưu ý: Đáp án có thể rất lớn, nên hãy in ra đáp án chia lấy dư cho ~10^9 + 7~.

Dữ liệu vào

• Dòng đầu gồm hai số nguyên ~N~ và ~sum~.
• Dòng thứ hai gồm ~N~ số nguyên ~arr[0], arr[1], \ldots, arr[N-1]~.

Kết quả

• Một số nguyên là số tập con có tổng bằng ~sum~, chia lấy dư cho ~10^9 + 7~.

Giới hạn

• ~1 \le N \cdot sum \le 10^6~
• ~0 \le arr[i] \le 10^6~

Sample Input 1

6 10
2 3 5 6 8 10

Sample Output 1

3

Giải thích

Các tập con: ~\{2, 3, 5\}~, ~\{2, 8\}~, ~\{10\}~.

Sample Input 2

5 10
1 2 3 4 5

Sample Output 2

3

Giải thích

Các tập con: ~\{1, 2, 3, 4\}~, ~\{1, 4, 5\}~, ~\{2, 3, 5\}~.

Nguồn: GeeksforGeeks (Medium).