Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

&nbsp;
Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].


Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 200
	1 &lt;= nums[i] &lt;= 100


class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2: return False
        total //= 2
        leng = len(nums)
        dp = [[False] * (total + 1) for _ in range(leng + 1)]
        
        for i in range(leng + 1): dp[i][0] = True
        for i in range(1, leng + 1):
            for j in range(1, total + 1):
                dp[i][j] = dp[i-1][j]
                if j - nums[i-1] >= 0:
                    dp[i][j] |= dp[i-1][j-nums[i-1]] 
        return dp[leng][total]
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i=0; i<nums.length; i++){
            sum = sum+nums[i];
        }
       
        if(sum%2 !=0){
            return false;
        }
        int[][] dp = new int[nums.length+1][sum];
        for(int i=0; i<dp.length; i++){
            Arrays.fill(dp[i],-1);
        }
       
        return helper(nums,sum/2,0,dp)>= 1? true : false;
    }
    public int helper(int[] nums, int sum, int i, int[][] dp){
        if(i==nums.length && sum==0){
            return 1;
        }
        if(i==nums.length){
            return 0;
        }
        if(sum < 0){
            return 0;
        }
        if(dp[i][sum] != -1){
            return dp[i][sum];
        }
        if(sum<nums[i]){
           return dp[i][sum] = helper(nums,sum,i+1,dp);
        }
        int a = helper(nums,sum-nums[i],i+1,dp); //Take the value
        int b = helper(nums,sum,i+1,dp); //Not take the value
        if(a==1 || b==1){   // if any of the options is returning true then whole answer would be true
                return dp[i][sum]=1;
        }else{
                return dp[i][sum]=0;
        }
    }
}
 class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        int n = nums.size();
        for(int i = 0;i<n;i++)
            sum = sum + nums[i];
        cout<<sum;
        
        if(sum % 2 == 0){
            int s = sum/2;
            int t[n+1][s+1];
            for(int i = 0; i<s+1;i++)
                t[0][i] = false;
            for(int i = 0;i<n+1;i++)
                t[i][0] = true;
            
            for(int i =1;i<n+1;i++){
                for(int j = 1; j<s+1;j++){
                    if(nums[i-1] <= j)
                        t[i][j] = t[i-1][j-nums[i-1]] || t[i-1][j];
                    else
                        t[i][j] = t[i-1][j];
                }
            }
            return t[n][s];
        }else
            return false;
    }
};
var canPartition = function(nums) {
    let sum = nums.reduce((prevVal, currValue) => prevVal + currValue, 0); // sum of each values
    if (sum % 2 !== 0) return false; // return false if odd sum
    
    let target = sum / 2;  // ex.[1,5,11,5]  target is half which is 11
    let dp = new Set(); // add unique values
    dp.add(0); //intialize with 0
    for (var i = nums.length - 1; i >= 0; i--) {  //start from end
        nextDp = new Set(); 
        for (const ele of dp.values()) {
           let newVal = ele + nums[i];
           if(newVal === target) return true; 
           nextDp.add(newVal); 
        }
        dp = new Set([...dp, ...nextDp]);
    }
    
    return false;
};
Partition Equal Subset Sum