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: trueExplanation: The array can be partitioned as [1, 5, 5] and [11].Example 2:Input: [1, 2, 3, 5]Output: falseExplanation: 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.
Partition Equal Subset Sum Challenge LeetCode
c++;performance;programming challenge;c++11;vectors
No need for full matrixAlthough 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 returnYour 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 rewriteHere 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;}