The 24 game, enumerate ways of reaching 24 from combinations of four numbers from 1 to 10

24all.c

#include <stdio.h>
#include <string.h>
#define N 20          /* max length of expression >= 2*ncard = 8 */
#define MAXDIG 10     /* max digit: note the digit should less than 42 */
int ncard = 4;        /* number of cards */
double target = 24;   /* target number */

#define zero(x) ((x) < 1e-5 && (x) > -1e-5)
#define clear(a) memset(a, 0, sizeof(a))

char expr[N], full[N][N]; /* expression */
double ans[N];
int  parent[N], sons[N], right[N];
int  pos, oprs, dad;
int  pool[MAXDIG + 1]; /* digits' pool */

char addmul[128]; /* maps '+' and '*' to '-' and '/' respectively, zero otherwise */
int  val[128];  /* numeric value for a number or operator */
int  rank[128]; /* rank of an operator, 0 for numbers */
#define isopr(ch) (rank[ch] > 0)

/* print expression(optimized infix notation output) */
char* print(char *p)
{
  char *q, ch = '\0';

  if (isopr(*p)) {
    if (p > expr) ch = expr[parent[p - expr]];

    if (rank[ch] > rank[*p]) putchar('('); /* add '(' if necessary */
      q = print(p + 1);
      putchar(*p);
      q = print(q);
    if (rank[ch] > rank[*p]) putchar(')');

    if (p == expr)  { putchar(';'); putchar(' '); }
    return q;
  } else {
    printf("%d", *p);
    return p + 1;
  }
}

/* compare two expression */
int expcmp(const char *s, const char *t)
{
  for ( ; *s == *t; s++, t++)
    if (*s == '\0')  return 0;
  return val[*s] - val[*t];
}

/* returns the next character */
char next(char c)
{
  switch (c) {
    case '+': return '-';
    case '-': return '*';
    case '*': return '/';
    case '/': c = '\0';
  }

  while(++c <= MAXDIG)
    if (pool[c] > 0) return c;

  return '\0';
}

void pop(void)
{
  if (isopr(expr[pos]))
    oprs++;
  else
    pool[ expr[pos] ]++;

  if (isopr(expr[pos]) || sons[parent[pos]] == 2)
    dad = parent[pos]; /* switch to the parent node */
  if (parent[pos] >= 0) sons[parent[pos]]--;
  pos--;
}

void push(char ch)
{
  /* pre-adjust ch, according to rule 1 & 2 */
  if (isopr(ch) && dad >= 0) {
    if (sons[dad] == 1) { /* ch is to add to right  */
      /* rule 1: adding to right, differs dad in rank */
      while(rank[ch] == rank[expr[dad]])
        ch = next(ch);
    } else { /* add to left */
      /* rule 2: '-' can't below '+' */
      if (addmul[expr[dad]] == ch)
        ch = next(ch);
    }
  }

  expr[++pos] = ch; /* add ch into expression */
  expr[pos + 1]='\0'; /* clear next byte */

  parent[pos] = dad; /* link: pos's parent = dad */
  if (dad >= 0 && ++sons[dad] == 2) /* add a son for 'dad' */
    right[dad] = pos; /* link: dad's right = pos */

  if (isopr(ch)) {
    dad = pos;
    oprs--;
  } else {
    int me = pos, cancel = 0;

    pool[ch]--;
    full[pos][0] = ch; full[pos][1]='\0';
    ans[pos] = (double) ch;
    /* set the new dad  and  generate full expression */
    while(dad >= 0 && sons[dad] == 2) {
      /* rule 3: left expr >= right expr */
      if ((addmul[expr[dad]] /* expr[dad] == '*' or '+' */
        && expcmp(full[dad + 1], full[me]) < 0)
      /* rule 4 : (c @ a) @ b, @ is any opr, a>=b */
      || (expr[dad] == expr[dad + 1] /* == '@' */
        && expcmp(full[right[dad + 1]], full[me]) < 0)) { /* a < b */
          cancel = 1;
      /* rule 5: a / 1 ==> 1*a; 0/a ==> 0*a */
      } else if (expr[dad] == '/') {
        if (zero(ans[me] - 1) || zero(ans[dad + 1])) cancel = 1;
      } else if (expr[dad] == '-') { /* a-0 ==> a+0 */
        if (zero(ans[me])) cancel = 1;
      }

      /* create full expression for dad */
      full[dad][0] = expr[dad]; full[dad][1]='\0'; /* opr */
      strcat(full[dad], full[dad + 1]); /* append left */
      strcat(full[dad], full[me]); /* append right */

      /* calcultate value of dad */
      switch (expr[dad]) {
        case '+': ans[dad] = ans[dad + 1] + ans[me]; break;
        case '-': ans[dad] = ans[dad + 1] - ans[me]; break;
        case '*': ans[dad] = ans[dad + 1] * ans[me]; break;
        case '/': ans[dad] = (zero(ans[me]) ?1E6 :ans[dad + 1]/ans[me]);
      }
      /* rule 6: eliminate negative answers */
      if (ans[dad] < -0.001) cancel = 1;

      me = dad;
      dad = parent[me];
    }

    /* change an opr: pop, and push next available */
    if (cancel) {
      pop();
      ch = next(ch);
      if (ch != '\0') push(ch);
    }
  }
}

int seek(int nums)
{
  char ch;
  int a = 0;

  clear(sons);
  oprs = nums - 1;
  dad = pos = -1;
  push('+');

  do{
    if (dad == -1) {
      if (oprs == 0 && zero(ans[0] - target)) {
        a++;
        print(expr);
      }
      pop();
    } else if (expr[pos + 1]=='\0') {
      if (oprs > 0)
        push('+');
      else
        push(next(0));
    } else {
      ch = next(expr[pos]);
      pop(); /* pop current opr, push next if necessary */
      if (ch != '\0') push(ch);
    }
  }while(isopr(expr[0]));

  return a;
}

/* return the number of permutations of (x[0], x[1], ..., x[n-1]) */
static int permut(const int x[], int n)
{
  int i, j, p = 1;
  static int fac[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

  p = fac[n];
  for (i = 0; i < n; ) { /* scan for identical numbers */
    for (j = i + 1; j < n && x[j] == x[i]; j++) ;
    p /= fac[j - i];
    i = j;
  }
  return p;
}

int main(int argc, char *argv[])
{
  int i, deg, cnt = 0, tot = 0, dcnt = 0, dtot = 0, st[10] = {0}, top = 0;

  /* initialize */
  rank['+'] = rank['-'] = 1; rank['*'] = rank['/'] = 2;
  addmul['+'] = '-'; addmul['*'] = '/';
  val['*'] = 104; val['/'] = 103; val['+'] = 102; val['-'] = 101;
  for (i = 1; i <= MAXDIG; i++) val[i] = MAXDIG - i;

  while (top >= 0) {
    if (top == ncard) {
      top--;
      tot++;
      deg = permut(st, ncard); /* number of permutations */
      dtot += deg;
      clear(pool);

      for (i = 0; i < ncard; i++) pool[st[i]]++;
      for (i = 0; i < ncard; i++) printf("%2d ", st[i]);
      printf(":  ");

      if (seek(ncard)) {
        cnt++;
        dcnt += deg;
      }

      printf("\n");
    } else if (++st[top] > MAXDIG) {
      st[top--] = 0;
    } else {
      st[top + 1] = st[top] - 1; /* eliminate duplicated cases, -1 as ++st[top] will increment it latter */
      /* to enumerate duplicated case: st[top + 1] = 0; */
      top++;
    }
  }
  printf("%g  %d %d  %d %d\n", target, cnt, tot, dcnt, dtot);
  return 0;
}