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;
}