Partition into two sets with equal sum

Given a multiset of integers, return whether it can be partitioned into two subsets whose sums are the same.

For example, given the multiset {15, 5, 20, 10, 35, 15, 10}, it would return true, since we can split it up into {15, 5, 10, 15, 10} and {20, 35}, which both add up to 55.

Given the multiset {15, 5, 20, 10, 35}, it would return false, since we can't split it up into two subsets that add up to the same sum.

Example:

Input:  arr[] = {15,5,20,10,35,15,10}
Output: true

Approach 1: Using Recursion

C++

#include <bits/stdc++.h>
using namespace std;

bool isPartitionSubstes(vector<int> &arr, int n, int sum)
{
    // if n is greater than size of array or
    //n is less than 0 then return false
    if (n >= arr.size() || n < 0)
        return false;

    //if sum is less than 0 then return false
    if (sum < 0)
        return false;

    //if sum becomes 0 then return true
    if (sum == 0)
        return true;
    return isPartitionSubstes(arr, n - 1, sum - arr[n]) ||
           isPartitionSubstes(arr, n - 1, sum);
}
int main()
{
    vector<int> arr = {15, 5, 20, 10, 35, 15, 10};

    int sum = 0;

    //find sum of array elements
    for (int i = 0; i < arr.size(); i++)
    {
        sum += arr[i];
    }
    if (isPartitionSubstes(arr, arr.size() - 1, sum / 2))
        cout << "true";
    else
        cout << "false";

    return 0;
}

Approach 2: Dynamic Programming 

Using Memoization

C++

#include <bits/stdc++.h>
using namespace std;

int dp[1000][1000];
bool isPartitionSubstes(vector<int> &arr, int n, int sum)
{

    //if n is greater than size of array or
    //n is less than 0 then return false
    if (n >= arr.size() || n < 0)
        return false;

    //if sum is less than 0 then return false
    if (sum < 0)
        return false;

    //if sum becomes 0 then return true
    if (sum == 0)
        return true;

    //if already calculated
    if (dp[n][sum] != -1)
        return dp[n][sum];

    //else calculate
    else
        dp[n][sum] =
            isPartitionSubstes(arr, n - 1, sum - arr[n]) ||
            isPartitionSubstes(arr, n - 1, sum);

    //return the dp[n][sum]
    return dp[n][sum];
}
int main()
{
    vector<int> arr = {15, 5, 20, 10, 35, 15, 10};

    int sum = 0;

    //find the sum of array elements
    for (int i = 0; i < arr.size(); i++)
    {
        sum += arr[i];
    }
    memset(dp, -1, sizeof(dp));

    if (isPartitionSubstes(arr, arr.size() - 1, sum / 2))
        cout << "true";
    else
        cout << "false";

    return 0;
}