leetcode 416 分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
记忆化搜索
代码：
class Solution { public: int f[200][20001] = {0}; bool dfs(vector<int> &nums,int k,int sum) { if(sum < 0 || k >= 200) return false; if(f[k][sum]) return f[k][sum] - 1; for(int i = k;i < nums.size();i ++) { if(dfs(nums,i + 1,sum - nums[i])) return f[k][sum] = 2; } return (f[k][sum] = 1) - 1; } bool canPartition(vector<int>& nums) { int sum = 0; for(int i = 0;i < nums.size();i ++) { sum += nums[i]; f[i][0] = 2; } if(sum % 2) return false; sum /= 2; for(int i = 0;i < nums.size();i ++) { if(dfs(nums,i + 1,sum - nums[i])) return true; } return false; } };