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 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:
", total);
for (i = 0; i < total; i++)
{
scanf ("%d", &a);
input[i] = a;
}
printf ("
");
count = combination (input, total, target, 0, stack);
printf ("There are %d sets of numbers that sum to %d.
", 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 ("
");
#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;
}

Copyright © Kenny Root. All rights reserved.