Last updated on July 18th, 2024 at 04:16 am

Here, We see Partition Equal Subset Sum LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Partition Equal Subset Sum LeetCode Solution

Problem Statement

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

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.

1. Partition Equal Subset Sum LeetCode Solution C++

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int resultant_sums = 0 ;
        for (auto x : nums)
            resultant_sums +=x;
        if(resultant_sums % 2) return false;
        resultant_sums /= 2;
        vector<bool> dp(resultant_sums+1,false);
        dp[0]=true;
        for(auto x:nums){
            for(int i=resultant_sums;i>=x;i--){
                dp[i] = dp[i] || dp[i-x] ;
            }
        }
        return dp[resultant_sums];
    }
};

2. Partition Equal Subset Sum LeetCode Solution Java

class Solution {
    boolean mem[][];
    public boolean canPartition(int[] nums) {
        int sum = 0;
        int n = nums.length;
        for(int i : nums) sum+=i;
        if(sum%2!=0) return false;
        sum /= 2;
        mem = new boolean[n+1][sum+1];
        return subsetSum(nums,0,sum);
    }
    boolean subsetSum(int[] nums, int pos, int sum){
        if(sum==0) return true;
        else if(pos>=nums.length || sum<0) return false;
        if(mem[pos][sum]) return true;
        return mem[pos][sum] = subsetSum(nums,pos+1,sum-nums[pos]) ||
                                subsetSum(nums,pos+1,sum);
    }
}

3. Partition Equal Subset Sum Solution JavaScript

var canPartition = function(nums) {
    var sum = nums.reduce((a, b) => a + b, 0);
    if (sum % 2 !== 0) {
        return false;
    }
    var half = sum / 2;
    var dp = [];
    dp[0] = true;
    for (var index = 0; index < nums.length; ++ index) {
        var num = nums[index];
        for (var i = half; i >= num; -- i) {
            dp[i] = dp[i] || dp[i - num];
        }
    }
    return dp[half] || false;
};

4. Partition Equal Subset Sum Solution Python

class Solution(object):
    def canPartition(self, nums):
        s, n = sum(nums), len(nums)
        memo = {(n,0):True}
        if s & 1: 
            return False
        nums.sort(reverse=True)
        def dfs(i, x):
            if x <= 0:
                return x == 0
            for j in range(i, n):
                if dfs(j+1, x-nums[j]):
                    return True
            return False
        return dfs(0, s >> 1)