#CS1628. 折半搜索 - Meet in the Middle

折半搜索 - Meet in the Middle

题目背景

翻译自 CSES-1628 题。

题目描述

给定一个包含 n 个数的数组，求有多少种方法可以从中选择一个子集，使得子集的和为 x。

输入格式

第一行包含两个整数 n 和 x，分别表示数组的大小和要求的和。

第二行包含 n 个整数 t1,t2,…,tnt_1,t_2,…,t_nt1​,t2​,…,tn​，表示数组中的数。

输出格式

输出一个整数，表示可以从数组中选择子集，使得该子集的和等于 x 的方法数。

样例

4 5
1 2 3 2

3

说明/提示

$1\le n \le 40$

$1 \leq x \leq 10^9$

1≤ti≤1091 \leq t_i \leq 10^91≤ti​≤109。