一、记忆化搜索
由于每个物品选的次数至多选一次，所以本题是一道标准的01背包问题。

定义 dfs(i,j) 表示从下标从[0, i]中前 (i + 1) 个物品中选一些，满足重量和恰好等于 j 的成功性。

考虑第 i 个物品 i 选或不选：

    ·不选：问题变成从前 i 个物品中选一些物品，满足重量和恰好等于 j 的成功性，即 dfs(i,j)=dfs(i−1,j)。
    ·选：问题变成从前 i 个完全平方数中选一些数（可以重复选），满足元素和恰好等于 j−i 的成功性， 即 dfs(i,j) |=dfs(i - 1, j − weight[i]);

            注意这里我们取或运算， 因为两个方案中成功一个即可。
 
递归边界：dfs(-1,0)=0，因为没有数可以选了，且要得到的数等于 0，那么答案为true。如果 j>0，那么 dfs(-1,j)=false。

                 dfs(i, <0) = false; 因为不能使得选的物品超过要的重量

递归入口：dfs(n - 1, S) 倒着从后面往前面选。

复杂度分析
时间复杂度：O(nS)，其中 n 为 nums 的长度，S 为 重量。由于每个状态只会计算一次，动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。本题状态个数等于 O(nS)，单个状态的计算时间为 O(1)，所以动态规划的时间复杂度为 O(nS)。
空间复杂度：O(nS)。保存多少状态，就需要多少空间。

#include <iostream>
#include <vector>
#include <functional>

using namespace std;

int main(void) {
	int S, n;
	cin >>...