Đếm Tập Con Theo Tổng · canuc80k0725

Cho dãy $a_{1}, \dots, a_{N}$ và số nguyên $S$ . Một tập con được chọn theo các vị trí của dãy; hai tập dùng các vị trí khác nhau được tính là hai tập khác nhau, kể cả khi các giá trị trùng nhau. Hãy đếm số tập con không rỗng có tổng bằng $S$ .

Input

Dòng đầu chứa $N$ và $S$ . Dòng thứ hai chứa $N$ số nguyên $a_{i}$ .

Output

In số tập con không rỗng có tổng đúng bằng $S$ .

Constraints

$1 \leq N \leq 20$ .
$∣ S ∣ \leq 1 0^{6}$ .
$∣ a_{i} ∣ \leq 1 0^{5}$ .

Scoring

Subtask $1$ ( $50%$ ): $N \leq 10$ .
Subtask $2$ ( $50%$ ): Không có giới hạn bổ sung.

Example

Test 1

Input

3 0
-1 0 1

Output

Giải thích: Ba tập chỉ số hợp lệ là ${0}, {- 1, 1}$ và ${- 1, 0, 1}$ . Tập rỗng không được tính, nên kết quả là $3$ .

Ý tưởng: Một tập con theo chỉ số được xác định bởi quyết định chọn hoặc bỏ từng phần tử. Cần lưu thêm cờ đã chọn ít nhất một phần tử để không tính tập rỗng khi mục tiêu bằng 0.
Thuật toán: DFS từ trái sang phải. Nhánh thứ nhất bỏ a[i]; nhánh thứ hai chọn nó, cộng vào tổng và đặt cờ chosen. Khi hết mảng, tăng đáp án nếu chosen đúng và tổng bằng S.
Tính đúng đắn: Mỗi tập chỉ số có đúng một đường chọn/bỏ nên được xét đúng một lần. Tổng được cập nhật chính xác theo các chỉ số đã chọn; cờ chosen đúng khi và chỉ khi tập không rỗng. Vì vậy điều kiện ở lá nhận đúng toàn bộ và chỉ các tập con không rỗng có tổng S.
Độ phức tạp: Thời gian O(2^N), bộ nhớ ngăn xếp O(N).