Two Sets II

Your task is to count the number of ways numbers 1,2,…,ncan be divided into two sets of the equal sum.

For example, if n=7, there are four solutions:

• {1,3,4,6} and {2,5,7}
  
• {1,2,5,6} and {3,4,7}
  
• {1,2,4,7} and {3,5,6}
  
• {1,6,7} and {2,3,4,5}

Example:

Input:  n = 7
Output: 4

Approach

C++

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

const int MOD = 1e9 + 7;

int twoSetsII(int n)
{

    if (n * (n + 1) % 4)
    {
        return 0;
    }
    int m = n * (n + 1) / 4;
    vector<int> dp(m + 1);
    dp[0] = 1;
    for (int i = 1; i < n; i++)
    {
        for (int j = m; j >= i; j--)
        {
            dp[j] = (dp[j] + dp[j - i]) % MOD;
        }
    }
    return dp[m];
}

int main()
{

    int n = 7;

    cout << twoSetsII(n) << "\n";

    return 0;
}