#include <iostream>
#include <math.h>
#include <string>

using namespace std;

bool isPrime(int n){
    if(n == 2 || n == 3){
        return true;
    }
    if(n % 2 == 0){
        return false;
    }
    int limit = (int)sqrt(n);
    for(int div = 3; div <= limit ; div += 2 ){
        if(n % div == 0){
            return false;
        }
    }
    return true;
}

int subsetSize = 3;
//int vals[]  = {3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99};
//int numVals = sizeof(vals)/sizeof(vals[0]);
int* vals ;
int numVals = 172;
int* subset;
int numSpecialSubsets = 0 ;

void p(string s, int a[], int l){
    cout << s << endl ;
    //int l = sizeof(a) / sizeof(a[0]);
    for(int i=0;i<l;i++){
        cout << a[i] << ",";
    }
    cout << endl;
}

void recur(int numRemaining, int subsetIndex, int valIndex) {
    subset[subsetIndex] = vals[valIndex];

    int start = valIndex+1;
    int end = numVals - numRemaining + 1;

    if(numRemaining == 2){
        for(int j=start; j<=end;j++){
            subset[subsetIndex+1] = vals[j];
            //p("", subset, subsetSize);
            int largest = subset[subsetSize-1];
            int sumOthers = 0;
            for(int k=0;k<subsetSize-1;k++){
                sumOthers += subset[k];
            }
            if(sumOthers == largest){
                numSpecialSubsets ++;
            }
        }
    }
    else{
        for(int j=start; j<=end;j++){
            recur(numRemaining-1, subsetIndex+1, j);
        }

    }
}

void level3(){
    for(subsetSize = 3; subsetSize <= numVals; subsetSize++){
        cout << subsetSize << " " << numSpecialSubsets << endl;
        int e = numVals-subsetSize+1;
        for(int i=0; i <= e; i++){
            subset = new int[subsetSize];
            recur(subsetSize, 0, i);
        }

    }
    cout << "level 2 : special subsets count = " << numSpecialSubsets << endl;
}


int main(){
    int np = 172;
    vals = new int[np];
    vals[0] = 2;
    int cand = 3;
    int i = 1;
    while(i < np){
        if(isPrime(cand)){
            vals[i++] = cand;
        }
        cand += 2;
    }
    numVals = np;
    p("",vals, np);
    level3();
}