Partition Equal Subset Sum Challenge LeetCode

Question

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.

Answer 1

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;

    // Read in numbers.
    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;
}