Bài tập | NEU OJ

Cửa hàng có $n$ mặt hàng giá $a_i$ . Khách muốn chọn đúng $k$ món có tổng giá đúng bằng $S$ . Hỏi có bao nhiêu cách chọn?

Vì $n \le 20$ nên có thể dùng đệ quy quay lui chọn/không chọn, cắt nhánh khi số phần tử còn lại không đủ.

Ví dụ: $n = 5$ , $k = 3$ , $S = 10$ , $a = [1, 2, 3, 4, 5]$ → $\{1, 4, 5\}, \{2, 3, 5\}$ → đáp án $2$ .

Định dạng đầu vào:
Dòng 1: $n$ , $k$ , $S$ . Dòng 2: $n$ số nguyên $a_i$ .
Ràng buộc đầu vào:
$1 \le n \le 20$ , $1 \le k \le n$ , $-10^9 \le S \le 10^9$ , $-10^7 \le a_i \le 10^7$ .
Định dạng đầu ra:
Một số nguyên — số tập con thoả mãn.

solution