Partition Equal Subset Sum Solutions in C++

// Source : https://leetcode.com/problems/partition-equal-subset-sum/description/
// Author : Hao Chen
// Date   : 2018-06-24



class Solution {
public:
    //back tracking
    bool canPartitionRecrusion(vector<int>& nums, int half, int index) {
        for (int i=index; i<nums.size(); i++){
            int h = half - nums[i];
            if ( h < 0 ) return false; //cannot found the solution
            if ( h == 0 ) return true; //found the solution
            if ( canPartitionRecrusion(nums, h, i+1) == true ) return true;
        }
        return false;
    }

    
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(auto n : nums) sum +=n;
        if ( sum & 1 ) return false; // sum % 2 !=  1
        int half = sum / 2;
        
        //sort the array in descending order
        //so, the DFS could be very fast to find the answer because it's greedy.
        std::sort(nums.begin(), nums.end(), std::greater<int>()); 

        //go to find a path which sum is half
        return canPartitionRecrusion(nums, half, 0);
    }
};

/// Source : https://leetcode.com/problems/partition-equal-subset-sum/description/
/// Author : liuyubobobo
/// Time   : 2017-11-19

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Memory Search
/// Time Complexity: O(len(nums) * O(sum(nums)))
/// Space Complexity: O(len(nums) * O(sum(nums)))
class Solution {

private:
    // memo[i][c]: using nums[0...i] to fill a back knapsack with space c
    vector<vector<int>> memo;

    bool tryPartition(const vector<int> &nums, int index, int sum){

        if(sum == 0)
            return true;

        if(sum < 0 || index < 0)
            return false;

        if(memo[index][sum] != -1)
            return memo[index][sum] == 1;

        memo[index][sum] = (tryPartition(nums, index - 1, sum) ||
               tryPartition(nums, index - 1, sum - nums[index])) ? 1 : 0;

        return memo[index][sum] == 1;
    }

public:
    bool canPartition(vector<int>& nums) {

        int sum = 0;
        for(int i = 0 ; i < nums.size() ; i ++){
            assert(nums[i] > 0);
            sum += nums[i];
        }

        if(sum % 2)
            return false;

        memo.clear();
        for(int i = 0 ; i < nums.size() ; i ++)
            memo.push_back(vector<int>(sum / 2 + 1, -1));
        return tryPartition(nums, nums.size() - 1, sum / 2);
    }
};


void printBool(bool res){
    cout << (res ? "True" : "False") << endl;
}

int main() {

    int nums1[] = {1, 5, 11, 5};
    vector<int> vec1(nums1, nums1 + sizeof(nums1)/sizeof(int));
    printBool(Solution().canPartition(vec1));

    int nums2[] = {1, 2, 3, 5};
    vector<int> vec2(nums2, nums2 + sizeof(nums2)/sizeof(int));
    printBool(Solution().canPartition(vec2));

    return 0;
}

/// Source : https://leetcode.com/problems/partition-equal-subset-sum/description/
/// Author : liuyubobobo
/// Time   : 2017-11-19

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Dynamic Programming
/// Time Complexity: O(len(nums) * O(sum(nums)))
/// Space Complexity: O(len(nums) * O(sum(nums)))
class Solution {

public:
    bool canPartition(vector<int>& nums) {

        int sum = 0;
        for(int i = 0 ; i < nums.size() ; i ++){
            assert(nums[i] > 0);
            sum += nums[i];
        }

        if(sum % 2)
            return false;

        int n = nums.size();
        int C = sum / 2;
        vector<bool> memo(C + 1, false);
        for(int i = 0 ; i <= C ; i ++)
            memo[i] = (nums[0] == i);

        for(int i = 1 ; i < n ; i ++)
            for(int j = C; j >= nums[i] ; j --)
                memo[j] = memo[j] || memo[j - nums[i]];

        return memo[C];
    }
};

void printBool(bool res){
    cout << (res ? "True" : "False") << endl;
}

int main() {

    int nums1[] = {1, 5, 11, 5};
    vector<int> vec1(nums1, nums1 + sizeof(nums1)/sizeof(int));
    printBool(Solution().canPartition(vec1));

    int nums2[] = {1, 2, 3, 5};
    vector<int> vec2(nums2, nums2 + sizeof(nums2)/sizeof(int));
    printBool(Solution().canPartition(vec2));

    return 0;
}