SubsetSums

This is an algorithm from an interview question a friend had at Amazon.com. It stumped him, but I wrote this program to show him how to solve it afterwards.

/* combi-kr.c** Written by Kenny Root, 2007/06/28**** Find subsets of a set of numbers that sum to a target value.**** To get more verbose output, compile with -DDEBUG set.*/#include <stdio.h>#include <stdlib.h>
int combination (int *, int, int, int, int *);int total;int *input;
#ifdef DEBUGint overall = 1;#endif
intmain (){  int i, a, count = 0;  int *stack;  int target;
  printf ("How many numbers do you want to enter? ");  scanf ("%d", &total);  input = malloc (sizeof (int) * total);  stack = malloc (sizeof (int) * total);
  printf ("What should the sum be? ");  scanf ("%d", &target);
  printf ("Enter string of %d numbers separated by a space:\n", total);  for (i = 0; i < total; i++)    {      scanf ("%d", &a);      input[i] = a;    }  printf ("\n");
  count = combination (input, total, target, 0, stack);  printf ("There are %d sets of numbers that sum to %d.\n", count, target);}
intcombination (int *numbers, int len, int compare_value, int depth, int *stack){  int i;  int count = 0;
  for (i = 0; i < len; i++)    {      if (numbers[i] == compare_value)        {          ++count;#ifdef DEBUG          int x, y = 0;
          stack[depth] = i + (total - len);
          /* Print out the stack match for debugging purposes. */          printf ("Match %-3d: ", overall++);
          for (x = 0; x < total; x++)            {              if (y <= depth && stack[y] == x)                {                  printf ("[%d] ", input[x]);                  ++y;                }              else                {                  printf (" %d  ", input[x]);                }            }          printf ("\n");#endif /* DEBUG */        }      else if (numbers[i] < compare_value)        {#ifdef DEBUG          stack[depth] = i + (total - len);#endif /* DEBUG */
          count +=            combination (numbers + i + 1, len - i - 1,                         compare_value - numbers[i], depth + 1, stack);        }    }
  return count;}