MAIN72

MAIN72 - Subset sum

#include <iostream>
#include <cstring>
using namespace std;

bool dp[100001][1001];
int arr[1001];

int main()
{
    int t, n;
    long long int sum;

    cin >> t;

    while(t--)
    {
        cin >> n;

        memset(dp, false, sizeof(dp));

        sum = 0;

        for(int i = 0; i < n; i++)
        {
            cin >> arr[i];
            sum += arr[i];
        }

        for(int i = 0; i < n; i++)
            dp[0][i] = true; // 0 sum

        for(int i = 1; i < n; i++)
            dp[i][0] = false; // sum is i but 0 element

        for(long int i = 1; i <= sum; i++)
        {
            for(int j = 1; j <= n; j ++)
            {
                dp[i][j] = dp[i][j - 1];

                if(i >= arr[j - 1])
                    dp[i][j] = dp[i][j] || dp[i - arr[j - 1]][j - 1];
            }
        }

        long int result = 0;

        for(int i = 1; i <= sum; i++)
        {
            if(dp[i][n])
                result += i;
        }


        cout << result << endl;


    }

    return 0;
}