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;#endifintmain (){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 DEBUGint 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 DEBUGstack[depth] = i + (total - len);#endif /* DEBUG */count +=combination (numbers + i + 1, len - i - 1,compare_value - numbers[i], depth + 1, stack);}}return count;}