U407992 子集和数

已知 $n+1$ 个正数：$w_{i}(1\leq i \leq n)$ 和 $M$ ，要求找出$\{w_{i}\}$ 的所有子集使得子集中元素之和等于 $M$ 。解采用大小固定的n-元组$(x_{1},...,x_{n})$ 表达，其中：$x_{i}\in\{0，1\}，1\leq i\leq n$ 。若$x_{i}=0$ ，表示解集合不包含 $w_{i}$ ；若 $x_{i}=1$，表示解集合包含 $w_{i}$。隐式约束条件是$\sum_{i=1}^nw_{i} x_{i} =M$。 要求利用回溯方法解决子集和数问题。

第一行为一个正整数 $n$ ，表示总集规模； 第二行是正整数 $M$ ，表示子集的和数； 第三行是总集中 $n$ 个正整数，中间用空格隔开。

如果有答案，则输出所有满足条件的子集（用固定长度n-元组表示符合条件的一个子集，即每行是一个长度为n的0/1序列），按字典序排列。 如果没有答案，则输出 `-1`

### 数据范围 $n\leq 20, \sum w_i,M\leq 10^9$ ### Bonus 想一想，若只要求判断是否有解，当 $n=40$ 时，有没有在**最坏情况下**仍能得到答案的算法？