/**

* Combination

*/

#define N 4

#define K 2

char parent[K];

void combination(int depth){

    if(depth==K-1){

        for(int i=0;i<K;i++){

            printf("%c ",parent[i]);

        }

        printf("

");

        return;

    }

    for(int i=parent[depth]+1-97;i<N;i++){

        parent[depth+1]=i+97;

        combination(depth+1);

    }

}

int main(){

    for(int i=0;i<N;i++){

        parent[0] = i+97;

        combination(0);

    }

}

#define N 300

int cache[N][N];

int binomial_coefficient(int n, int r){

    //basis example

    if(r==0 || n==r){return 1;}

    if(cache[n-1][r-1]==-1){

        cache[n-1][r-1] = binomial_coefficient(n-1,r-1);

    }

    if(cache[n-1][r] == -1){

        cache[n-1][r] = binomial_coefficient(n-1,r);

    }

    return cache[n-1][r-1]+cache[n-1][r];

}

void main(){

    for(int i=0;i<N;i++){

        for(int j=0;j<N;j++){

        cache[i][j]=-1;

        }

    }

    printf("%d

",binomial_coefficient(250,12));

}

//Time complexity less than P!

//#define N 2

//#define K 2

//#define C 1

//int friends[C*2]={0,1};

//#define N 4

//#define K 4

//#define C 6

//int friends[C*2]={0,1,1,2,2,3,3,0,0,2,1,3};

#define N 6

#define K 6

#define C 10

int friends[C*2]={0,1,0,2,1,2,1,3,1,4,2,3,2,4,3,4,3,5,4,5};

int parent[K];

int pN=0;

bool isFriendlySelected(){

    for(int i=0;i<K;i+=2){

        bool isFriend=false;

        for(int j=0;j<C*2;j+=2){

            if(friends[j]==parent[i] && friends[j+1]==parent[i+1] ){

                    isFriend = true;

                break;

            }

        }

        if(!isFriend){

            return false;

        }

    }

    return true;

}

void permutation(int depth){

    if(depth==K-1){

        if(isFriendlySelected()){

            pN++;

        }

        return;

    }

    for(int i=0;i<N;i++){

        bool goFurther=true;

        for(int j=0;j<=depth;j++){

            if(parent[j]==i){

                goFurther=false;

                break;

            }

        }

        if(goFurther && (depth <2 || parent[depth-2] <parent[depth])){

            parent[depth+1]=i;

            permutation(depth+1);

        }

    }

}

int main(){

    for(int i=0;i<N;i++){

        parent[0] = i;

        permutation(0);

    }

    printf("%d

",pN);

}