/**
* 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);
}