4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.