/**
knakul853
**/
class Solution {
public:
    bool canPartition(vector<int>& nums) {

        int sm = accumulate(nums.begin(), nums.end(),0);
        if(sm&1)return 0;
        sm/=2;
        int n = nums.size();

        vector<vector<int>>dp(n+1, vector<int>(sm+1, -1));

        return f(nums, 0, sm, dp);

    }

    bool f(vector<int>&nums, int id, int target, vector<vector<int>>&dp)
    {
        if(target == 0)
            return true;
        if(target<0 || id == nums.size())
        {
            return false;
        }

        if(dp[id][target]!=-1)return dp[id][target];

        bool res = f(nums, id+1, target, dp) | f(nums, id+1, target - nums[id], dp);
     return dp[id][target] = res;
    }
};