416. Partition Equal Subset Sum.cpp

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