# Partition Equal Subset Sum Challenge LeetCode

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.

### No need for full matrix

Although your dynamic programming solution works, you are using a matrix of size [sum/2][n] when you only need to allocate a single vector of size [sum/2]. Not only are you using more memory than necessary, but this could also affect performance because of caching.

### Use a quick return

Your solution runs the full double loop to completion before determining whether the answer is possible. It is possible to create a solution that returns as soon as it finds a valid solution. This could potentially cut down on the time by a lot for inputs that have solutions.

Additionally, I found that sorting the inputs and looping through them from largest to smallest works best in conjunction with the quick return.

### Sample rewrite

Here is how I would write the program, using only a single dimensional vector for the DP part, sorting the inputs, and allowing for a quick return:

#include <iostream>
#include <vector>
#include <algorithm>

int main(void)
{
int n;
int sum = 0;

std::cin >> n;
std::vector<int> nums(n);
for (int i=0; i<n; i++) {
int num;
std::cin >> num;
nums[i] = num;
sum    += num;
}

// Quick check to see if sum is even.
if (sum & 1) {
std::cout << "false" << std::endl;
return 0;
}
// Cut sum in half.  Sum is now the target to reach.
sum >>= 1;

// Sort numbers so we can use the largest ones first.
sort(nums.begin(), nums.end());

// Iterate through each number from largest to smallest, updating the
// possible array and trying to find out if [sum] is possible.
std::vector<bool> possible(sum);
possible[0] = true;
for (int i=n-1; i>=0; i--) {
int val = nums[i];
// Quick return if we find we can reach [sum].
if (sum - val >= 0 && possible[sum - val]) {
std::cout << "true" << std::endl;
return 0;
}
for (int j=sum-val-1; j >= 0; j--) {
if (possible[j])
possible[j + val] = true;
}
}

std::cout << "false" << std::endl;
return 0;
}