# Partition Equal Subset Sum Leetcode Solution

## Partition Equal Subset Sum Leetcode Problem :

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.

## Partition Equal Subset Sum Leetcode Solution :

### Constraints :

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

### Example 1:

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

Intuition :

The problem is a classic example of a partition problem, where you need to divide an array into two subsets with equal sums. The intuition here is to use dynamic programming to keep track of whether it’s possible to achieve a specific sum using elements from the input array.

Approach :
1. Calculate the total sum of all elements in the input array nums. If the sum is odd, it’s impossible to partition the array into two equal subsets, so return false.
2. Calculate the target sum for each subset, which is sum /2.
3. Initialize a boolean array dp of size req + 1 (where req is the target sum) to keep track of whether it’s possible to reach a certain sum using elements from the input array. Initialize dp[0] to true.
4. Use a nested loop to iterate over the elements in the nums array and update the dp array. The outer loop iterates over the elements in nums, and the inner loop iterates from req down to nums[i]. For each element nums[i], update dp[j] to be true if either dp[j] was already true or dp[j – nums[i]] is true.
5. After completing the loops, check if dp[req] is true. If it is, return true, indicating that it’s possible to partition the array into two subsets with equal sums. Otherwise, return false.

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

## Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others