p5723 【深基4.例13】质数口袋

题目描述：

给定 $n$ 个正整数 $a_1,a_2,\dots,a_n$，从中选出若干个数，使它们的和恰好为 $S$。若 $S$ 可以表示成质数，输出 YES，否则输出 NO。

输入格式：
第一行包含整数 $n$ 和 $S$。
第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式：
输出 YES 或 NO。

数据范围：
$1\leq n\leq 20$
$2\leq S\leq 5000$
$1\leq a_i\leq 1000$

样例：

输入：
4 13
1 2 4 7
输出：
YES

输入：
5 8
1 2 4 5 7
输出：
NO

解题思路：

本题可以通过深度优先搜索的方式来解决。

我们可以从第一个数字开始，对于每个数字，可以选择或者不选择，因为这是一个背包问题，因此对于每一个选择的状态，我们可以将其转化为一个状态，从而可以使用记忆化搜索来提高效率。

同时，本题涉及到判断一个数字是否为质数，我们可以通过判断是否存在 $2\sim \sqrt x$ 的因子来判断是否为质数。由于判断质数是一个常用的操作，我们可以将这个函数写成一个函数，并在主函数中调用即可。