SubsetSums

/* 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 DEBUG
int overall = 1;
#endif
 
int
main ()
{
  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);
}
 
int
combination (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;
}