Bài 14.1. Đếm Số Cách Phân Bổ Ngân Sách - [Độ khó: Khá]

Trong một thế giới ảo, bạn là một nhà quản lý sự kiện chịu trách nhiệm tổ chức Lễ Hội Sắc Màu. Để làm cho lễ hội trở nên ấn tượng, bạn có một danh sách \(N\) loại pháo hoa khác nhau, mỗi loại có một giá trị chi phí nhất định. Bạn có một ngân sách tổng cộng là \(S\) đồng. Bạn cần tìm tất cả các cách có thể để chọn ra một số loại pháo hoa sao cho tổng chi phí của chúng đúng bằng \(S\). Mỗi loại pháo hoa chỉ có thể được chọn tối đa một lần.

Hãy viết một chương trình đệ quy để tính toán số lượng các cách phân bổ ngân sách đúng bằng \(S\).

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(S\) (\(1 \le N \le 20\), \(1 \le S \le 1000\)). Dòng thứ hai chứa \(N\) số nguyên dương \(cost_1, cost_2, \dots, cost_N\) (\(1 \le cost_i \le 100\)) là chi phí của từng loại pháo hoa.

OUTPUT FORMAT

In ra một số nguyên duy nhất là tổng số cách chọn các loại pháo hoa có tổng chi phí bằng \(S\).

Ví dụ:

Input:

3 30
10 20 30

Output:

2

Giải thích: Bạn có 3 loại pháo hoa với chi phí lần lượt là 10, 20, 30 và ngân sách mục tiêu là 30. Có 2 cách để đạt tổng chi phí là 30:

1. Chọn pháo hoa loại 3 có chi phí 30.
2. Chọn pháo hoa loại 1 (chi phí 10) và pháo hoa loại 2 (chi phí 20). Vì vậy, kết quả là 2.