Last updated on February 2nd, 2025 at 06:07 am

Here, we see a Partition Equal Subset Sum LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Dynamic Programming

Companies

Ebay

Level of Question

Medium

Partition Equal Subset Sum LeetCode Solution

1. 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.

2. Coding Pattern Used in Solution

The coding pattern used here is 0/1 Knapsack. This is because:

• We are deciding whether to include or exclude each number in the subset.
• The problem involves finding a subset that satisfies a specific condition (sum equals half of the total sum).

3. Code Implementation in Different Languages

3.1 Partition Equal Subset Sum 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];
    }
};

3.2 Partition Equal Subset Sum 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.3 Partition Equal Subset Sum 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;
};

3.4 Partition Equal Subset Sum 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)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n * m)	O(m)
Java	O(2n)	O(n * m)
JavaScript	O(n * m)	O(m)
Python	O(2n)	O(n)

• The C++ and JavaScript implementations are more efficient in terms of time and space complexity because they use an iterative DP approach with a 1D array.
• The Java and Python implementations use recursion with memoization, which is less efficient for large inputs due to the exponential time complexity of recursion.
• All implementations follow the 0/1 Knapsack pattern, where we decide whether to include or exclude each number to achieve the target sum.