Dare2Solve
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.
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.
nums
.false
as it is impossible to partition the array into two equal subsets.sum / 2
.dp
where dp[i]
represents whether a subset with sum i
can be formed using the elements in nums
.dp[0]
to true
because a subset with sum 0 is always possible (the empty subset).nums
, update the dp
array from right to left to ensure that each number is only used once.dp[target]
, which indicates whether a subset with the target sum exists.O(n * sum/2), where n
is the length of nums
and sum/2
is the target sum.
O(sum/2) for the dp
array.
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2 != 0) {
return false;
}
int half = sum / 2;
vector<bool> 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];
}
};
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]
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];
}
}
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;
};