#include <stdio.h>

#define DIGITSL 10
#define MAXDL (DIGITSL+2)

int digits[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int maxd[MAXDL];

struct lstStruct {
  int val;
  struct lstStruct * nxt;
  struct lstStruct * pre;
};
typedef struct lstStruct lstS;

lstS lstG[DIGITSL];
lstS* init_lst() {
  int i;
  for (i=0; i<DIGITSL; i++) {
    lstG[i].val = i;
    if (i) lstG[i].pre = &lstG[i-1];
    if ((DIGITSL-1)-i) lstG[i].nxt = &lstG[i+1];
  }
  return &lstG[0];
}
lstS* rm_lst(lstS *ol, lstS *l) {
  if (l->pre) l->pre->nxt = l->nxt;
  if (l->nxt) l->nxt->pre = l->pre;
  return (ol!=l) ? ol : l->nxt;
}
lstS* ad_lst(lstS *ol, lstS *l) {
  if (l->nxt) l->nxt->pre = l;
  if (l->pre) l->pre->nxt = l;
  return (l->pre) ? ol : l;
}

int cnt;

void seq(int n, int atmax, lstS * lst, long long s, int left ) {
  int limit, childmaxd;
  lstS *l;
  if (n==1) {
    s *= 10;
    for (l = lst; l; l=l->nxt) {
/*       printf("%lld \n", s+l->val); */
      if (s+l->val) cnt++;
    }
    return;
  }
  limit = atmax ? maxd[n] : DIGITSL-1;

  childmaxd = 0;
  s *= 10;
  for (l = lst; l ; l = l->nxt) {
    if (l->val <= limit) {
      childmaxd = atmax && (l->val == limit);

      if (left && (l->val == 0))
        seq(n-1, childmaxd, lst, s, 1);
      else {
        seq(n-1, childmaxd, rm_lst(lst, l), s+l->val, 0);
	ad_lst(lst, l);
      }
    }else
      break;
  }
}

int main() {
  int n=11;
  maxd[n]=1;
  seq(n, 1, init_lst(), 0, 1);
  printf("cnt: %d\n", cnt);
  return 0;
}

cnt: 8877690