#include <iostream>

using namespace std;

int checkSum(int array[], int size, int sum){

    int cache[size+1][sum+1];
    int counter = 0;

    cache[0][0]=false;
    for (int i=1;i<=size;i++){
        int value = 0;
        for (int j=0;j<=sum;j++){
            value+=array[j];
            if (array[i]<value){
                cache[i][j]=true; // true if the values to the right are less than the sums to the left
            }
        }
    }

    for (int i=1;i<=size;i++){
        for (int j=1;j<=sum;j++){
            if (array[i-1] > j){
                cache[i][j] = cache[i-1][j];
            } else {
                cache[i][j] = cache[i-1][j] || cache[i-1][j-array[i-1]];
                if (cache[i][j]==true){
                    counter+=1; // counter of how many times the condition is met
                }
            }
        }
    }

    return counter;
}

int partition(int array[], int size){ // function that partitions by putting together the elements of the set one by one since the partitons are contiguous anyway
    int sum=0;
    int total=0;
    for (int i=0;i<size;i++){
        sum+=array[i];
        total+=checkSum(array,size,sum);
    }
    return total;

}

int main(){
    int array[] = {1,2,3,4,5};
    int size = 5;
    cout << partition(array,size) << "n";
    return 0;
}

{1}{2}{3}{4}{5}
{1}{2}{3}{4,5}
{1}{2,3}{4,5}
{1}{2}{3,4,5}
{1}{2,3,4,5}
{1,2}{3,4,5}
{1,2,3}{4,5}