I solved this problem in LeetCode.
Given a non-empty array 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.
Note: Each of the array element will not exceed 100. The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for(auto it = nums.begin(); it != nums.end(); ++it)
{
sum += (*it);
}
if((sum % 2 != 0) || nums.size() <= 1)
{
return false;
}
vector < vector < bool > > isValid((sum /2) + 1, vector < bool > (nums.size() + 1, false));
for(int i = 0; i <= nums.size(); ++i)
{
isValid[0][i] = true;
}
for(int row = 1; row <= (sum/2); ++row)
{
for(int col=1; col<= nums.size(); ++col)
{
if(row >= nums[col - 1])
{
isValid[row][col] = isValid[row][col -1] || isValid[row - nums[col - 1]][col-1];
}
else
{
isValid[row][col] = isValid[row][col -1];
}
}
}
return isValid[sum/2][nums.size()];
}
};
The approach was a pretty straightforward DP implementation which is O(sum * n)
in terms of space and time complexity.
My solution took about 1382 ms
to execute all the 1183 test cases while I saw solutions which executed in about 200 ms
in the same language.
As far as I know there isn't a greedy solution to this problem, only approximations algorithm exist for this.
Can you suggest if there exists a solution with better time complexity for this problem or if my implementation has some redundant initialization or iterations which slow it down.