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