Problem
Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
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.
Constraints:
1 <= nums.length <= 2001 <= nums[i] <= 100
Solution (Java)
class Solution {
public boolean canPartition(int[] nums) {
int totalSum = 0;
for(int i=0;i<nums.length;i++)
totalSum+=nums[i];
if(totalSum % 2 != 0)
return false;
int sum = totalSum/2;
return IsHalfSumAvailable(nums,sum);
}
public boolean IsHalfSumAvailable(int[] nums, int sum)
{
boolean [][] dp = new boolean[nums.length+1][sum+1];
for(int i=0;i<=sum;i++)
dp[0][i] = false;
for(int i=0;i<=nums.length;i++)
dp[i][0] = true;
for(int i=1;i<=nums.length;i++)
{
for(int j=1;j<=sum;j++)
{
if(nums[i-1] > j)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
}
}
return dp[nums.length][sum];
}
}
Solution (Javascript)
/**
* @param {number[]} nums
* @return {boolean}
*/
var canPartition = function(nums) {
const sum = nums.reduce((acc, number) => number + acc, 0)
if (sum % 2 !== 0) {
return false
}
const memo = {}
const aux = (index, current = 0) => {
memo[index] = memo[index] || {}
if (memo[index][current] !== undefined) {
return memo[index][current]
}
if (current > sum / 2) {
return false
}
if (current === sum / 2) {
return true
}
if (index > nums.length) {
return false
}
memo[index][current] = aux(index + 1, current + nums[index]) || aux(index + 1, current)
return memo[index][current]
}
return aux(0, 0)
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).