🎨Now live: Try our Free AI Image Generation Feature

Description
Given a non-empty array of positive integers nums
, determine if it can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Intuition
The problem can be reduced to finding if there exists a subset of nums
that sums up to sum / 2
, where sum
is the total sum of the elements in nums
. If the total sum is odd, it is impossible to partition the array into two equal subsets.
Approach
- Calculate the total sum of the elements in
nums
. - If the total sum is odd, return
false
as it is impossible to partition the array into two equal subsets. - Set the target sum to be
sum / 2
. - Use dynamic programming to determine if there exists a subset with sum equal to the target sum.
- Create a boolean array
dp
wheredp[i]
represents whether a subset with sumi
can be formed using the elements innums
. - Initializedp[0]
totrue
because a subset with sum 0 is always possible (the empty subset). - For each number innums
, update thedp
array from right to left to ensure that each number is only used once. - Return the value of
dp[target]
, which indicates whether a subset with the target sum exists.
Complexity
Time Complexity:
O(n * sum/2), where n
is the length of nums
and sum/2
is the target sum.
Space Complexity:
O(sum/2) for the dp
array.
Code
C++
class Solution {
public:
bool canPartition(vector& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2 != 0) {
return false;
}
int half = sum / 2;
vector dp(half + 1, false);
dp[0] = true;
for (int num : nums) {
for (int i = half; i >= num; --i) {
dp[i] = dp[i] || dp[i - num];
}
}
return dp[half];
}
};
Python
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total_sum = sum(nums)
# If the total sum is odd, we can't split it into two equal subsets
if total_sum % 2 != 0:
return False
target = total_sum // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for i in range(target, num - 1, -1):
dp[i] = dp[i] or dp[i - num]
return dp[target]
Java
class Solution {
public boolean canPartition(int[] nums) {
int sum = Arrays.stream(nums).sum();
if (sum % 2 != 0) {
return false;
}
int half = sum / 2;
boolean[] dp = new boolean[half + 1];
dp[0] = true;
for (int num : nums) {
for (int i = half; i >= num; --i) {
dp[i] = dp[i] || dp[i - num];
}
}
return dp[half];
}
}
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;
};