Code:
#include <stdio.h>
#include <limits.h>
#include <string.h>
#ifndef ULONG_BITS
#define ULONG_BITS (CHAR_BIT * sizeof (unsigned long))
#endif /* ULONG_BITS */
int main(int argc, char *argv[])
{
long number[ULONG_BITS];
long term[ULONG_BITS];
long total, sum;
unsigned long proposal, solutions, left;
int numbers, terms, i, n;
char dummy;
if (argc < 5 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
fprintf(stderr, "\n");
fprintf(stderr, "Usage: %s [ -h | --help ]\n", argv[0]);
fprintf(stderr, " %s TERMS SUM N1 [ N2 .. ] NN\n", argv[0]);
fprintf(stderr, "\n");
fprintf(stderr, "This will output the number of unique sums\n");
fprintf(stderr, "totaling SUM when TERMS nonrepeating terms\n");
fprintf(stderr, "from the specified set, N1 to NN, are summed.\n");
fprintf(stderr, "\n");
return 0;
}
numbers = argc - 3;
if (numbers < 2) {
fprintf(stderr, "Too few numbers specified.\n");
return 1;
}
if (numbers >= (int)ULONG_BITS) {
fprintf(stderr, "Too many numbers specified (max %d).\n", (int)ULONG_BITS - 1);
return 1;
}
if (sscanf(argv[1], " %d %c", &terms, &dummy) != 1) {
fprintf(stderr, "%s: Invalid number of terms in the sums.\n", argv[1]);
return 1;
}
if (terms < 2) {
fprintf(stderr, "%s: Too few terms in the sums.\n", argv[1]);
return 1;
}
if (terms >= numbers) {
fprintf(stderr, "%s: Too many terms in the sums.\n", argv[1]);
return 1;
}
if (sscanf(argv[2], " %ld %c", &total, &dummy) != 1) {
fprintf(stderr, "%s: Invalid total; not an integer.\n", argv[2]);
return 1;
}
for (i = 0; i < numbers; i++)
if (sscanf(argv[i+3], " %ld %c", &number[i], &dummy) != 1) {
fprintf(stderr, "%s: Invalid number; not an integer.\n", argv[i+3]);
return 1;
}
/* There are 2**numbers possible solutions in the superset containing
* the desired solution. */
proposal = 1UL << numbers;
/* No solutions found yet. */
solutions = 0UL;
while (proposal-- > 0UL) {
/* Each bit in 'left' refers to each 'number'. */
left = proposal;
/* Sum matching this proposal. */
sum = 0L;
/* 'n' is the number of terms in the sum. */
n = 0;
/* 'i' corresponds to the bit number at the least significant position. */
i = 0;
while (left && i < numbers && n < terms) {
/* Was bit 'i' set in 'proposal'? */
if (left & 1UL) {
/* Yes, add number 'i' to the sum. */
term[n] = number[i];
sum += number[i];
/* A number was added to the sum. */
n++;
}
left >>= 1UL;
i++;
}
/* For 'proposal' to be a true solution:
* 'sum' must equal 'total'
* 'n' must equal 'terms' (i.e. 'terms' numbers used)
* 'left' must be zero (exactly 'terms' bits in 'proposal' set)
*/
if (sum != total || n != terms || left)
continue;
/* 'proposal' matches a true solution. */
solutions++;
printf("Solution %lu. %ld", solutions, term[0]);
for (i = 1; i < terms; i++)
printf(" + %ld", term[i]);
printf(" = %ld\n", sum);
}
printf("Found %lu solutions.\n", solutions);
return 0;
}
This has the nice side effect of being able to work on any numbers as terms in the sum, not just decimal digits. For example, if you compile the above to