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& nums) {
        int sum = 0;
        for(auto it = nums.begin(); it != nums.end(); ++it)
        {
            sum += (*it);
        }

        if((sum % 2 != 0) || nums.size()  > isValid((sum /2) + 1, vector  (nums.size() + 1, false));

        for(int i = 0; i = 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 
#include 
#include 

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

    // Read in numbers.
    std::cin >> n;
    std::vector nums(n);
    for (int i=0; i> num;
        nums[i] = num;
        sum    += num;
    }

    // Quick check to see if sum is even.
    if (sum & 1) {
        std::cout >= 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 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 = 0; j--) {
            if (possible[j])
                possible[j + val] = true;
        }
    }

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

StackExchange Code Review Q#148157, answer score: 3