// Author: Manfred Scheucher // Date : 29.05.2015 #include<assert.h> #include<stdlib.h> #include<stdio.h> #define MAXN 10 long ct = 0; int x[1<<MAXN]; int search(int n,int maxk,int term,int valid_so_far) { if(n==0) { ct++; //if(ct%1000000==0) printf("count: %ld\n",ct); if(valid_so_far) { printf("found: %ld\n",ct); exit(0); } } else { if(maxk>n) maxk=n; int k; int still_valid; for(k=maxk;k>0;k--) { still_valid = valid_so_far ? (x[term]==k) : 0; search(n-k,k,term+1,still_valid); } } } int binomial(int n,int k) { if(k>n || k<0) return 0; if(k==0 || k==n) return 1; return binomial(n-1,k-1)+binomial(n-1,k); } int main(int argc,char** argv) { int n = atoi(argv[1]); int i; printf("row: "); for(i=0;i<=n;i++) { x[i] = binomial(n,(n-i)/2); printf("%d ",x[i]); } x[n+1]=0; printf("\n"); assert(n < MAXN); search(1<<n,1<<n,0,1); // 1<<n = 2^n printf("failed after %ld\n",ct); }