class Solution { public: bool solve(vector<int>& nums, int sum, int curr, int idx, vector<vector<int>>& dp) { if(curr==sum) return true; if(curr>sum||idx==nums.size()) return false; if(dp[curr][idx]!=-1) return dp[curr][idx]; bool ck=false; ck=ck|solve(nums, sum, curr+nums[idx], idx+1, dp); ck=ck|solve(nums, sum, curr, idx+1, dp); return dp[curr][idx]=ck; } bool canPartition(vector<int>& nums) { int s=0; int n=nums.size(); for(int i=0;i<n;i++) { s+=nums[i]; } vector<vector<int>> dp(s+1, vector<int>(nums.size(), -1)); if(s%2==1) return false; else return solve(nums, s/2, 0, 0, dp); } };