恰好K件的凑和选法

难度：T2

【知识点：递归枚举、搜索剪枝】

前置知识：数组、函数、递归状态、可行性与顺序规则。

题目描述

有 $n$ 件按编号区分的物品，重量为正整数 $a_i$。每件至多选择一次。求恰好选择 $K$ 件且总重量恰好为 $S$ 的选法数。顺序不构成新选法；不同编号即使重量相同仍是不同物品。$K=0$ 时只允许空选择，其重量为 $0$。

输入格式

第一行三个整数 $n,S,K$。第二行 $n$ 个整数 $a_1,\ldots,a_n$。

输出格式

一行一个整数，表示恰好选择 $K$ 件且总重量为 $S$ 的选法数；没有则输出 $0$。

样例输入

3 6 2
2 4 5

样例输出

1

样例解释

只选第 $1,2$ 件，恰好两件且重量为 $6$。

数据范围

$1\le n\le20$，$0\le K\le n$，$0\le S\le20000$，$1\le a_i\le1000$。