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.
Example :
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
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 :
- 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.
- Calculate the target sum for each subset, which is sum /2.
- 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.
- 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.
- 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.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
C++
Java
Python
C++
class Solution {
public:
bool canPartition(vector< int>& nums) {
int sum = 0;
for (int num : nums)
sum += num;
if (sum % 2 != 0)
return false;
int req = sum / 2;
int n = nums.size();
vector< bool> dp(req + 1, false);
dp[0] = true;
for (int i = 0; i < n; i++) {
for (int j = req; j >= nums[i]; j--) {
dp[j] = dp[j] || dp[j - nums[i]];
}
}
return dp[req];
}
};
Java
class Solution {
public boolean canPartition(int[] nums) {
int sum=0;
for(int i:nums)sum+=i;
if(sum%2!=0)return false;
int req=sum/2;
int n=nums.length;
boolean[] dp=new boolean[req+1];
dp[0]=true;
for(int i=0;i=nums[i];j--){
dp[j]=dp[j] || dp[j-nums[i]];
}
}
return dp[req];
}
}
Python
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total_sum = sum(nums)
if total_sum % 2 != 0:
return False
req = total_sum // 2
n = len(nums)
dp = [False] * (req + 1)
dp[0] = True
for i in range(n):
for j in range(req, nums[i] - 1, -1):
dp[j] = dp[j] or dp[j - nums[i]]
return dp[req]
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
Login/Signup to comment