Subset Sum DP

subset_sum.cpp

#include <bits/stdc++.h>
using namespace std;
void printer(int** a, int r, int c)
	{
		cout << endl;
		for (  int i = 0 ; i <= r ; i++ )
			{
				for ( int j = 0 ; j <= c ; j++ )
					{
						cout << a[i][j] << " ";
					}
				cout << endl;
			} 
	}
int main()
	{
		int t, n, sum, sumi;
		t = 1;
		cin >> t;
		while ( t-- )
			{
				n = 28;
				cin >> n;
				sum = n * (n+1) / 2;
				long long** a = new long long*[n+1];
				for ( int i = 0 ; i <= n ; i++ )
					{
						a[i] = new long long[sum+1];
					}
				for ( int i = 0 ; i <= n ; i++ )
					{
						for ( int j = 0 ; j <= sum ; j++ )
							{
								a[i][j] = 0;
							}
					}
				a[0][0] = 1;
				for ( int i = 1 ; i <= n; i++ )
					{
						for ( int j = 0 ; j <= sum ; j++ )
							{
								if ( j < i )
									a[i][j] = a[i-1][j];
								else
									{
										a[i][j] = a[i-1][j] + a[i-1][j-i];
									}
							}
					}
				int sumi = 0;
				//printer(a, n, sum);
				for ( int j = 0 ; j <= sum ; j++ )
					{
						sumi = (sumi % 1000000007 + (a[n][j]*j) % 1000000007)% 1000000007;
					}
				cout << sumi % 1000000007 << endl;
			}
	}