Thread: Combinations of given number that add up to X

Hi,

Though it shouldn't be really difficult, I've been kind of stuck with this. I need to make a function, that computes and shows all the possible combinations (without repetition) of given number, where the digits (that only range from 1 to 9) of every combination give a specified sum when added.


I guess it's not the clearest explanation, so here is an example: Calculate all sets of 5 numbers (from 1 to 9) that add up to 28.


I would be really grateful, if someone could explain this.

I read it, but I really can't see a way of doing this.
At least, I would like to know if I need to calculate ALL the combinations, and then filter the ones that don't match the sum, or is there a faster way?

This is Sunday, traditionally a non-work day, so we pull the answers right out of our asses.

j/k

This can be brute force searched in about 1 second.

let's say you have an int array a[5], and you set it to the lowest possible combination of digits equal to 28: 11899, but you wanted the number to be reversed, so it looked just like this, instead of like:

Code:

int a[5]={1,1,8,9,9};

which when incremented the normal way, would be:
21899
31899
41899
etc.
Not what I wanted, so I used

Code:

a[5]={9,9,8,1,1},

which when viewed the normal way, displays as:

11899
11911
11912
11913
etc.

Code:

 
length = 5;

while(k<length) {
   while(a[0] < 10)
      if(a[4]+a[3]+a[2]+a[1]+a[0]==28) 
         for(m=4;m>-1;m--)   //print it reversed, and work from it reversed
            printf("%d",a[m])   //"normal" number format
         printf("\n")
         //getchar()
         count++      
      }
      increment a[0]
   }
   decrement a[0]   //one too far, back up

   //adjust the higher columns (index number) of digits
   k=0;
   while(a[k]==9)  //find the next digit < 9
      ++k     

   ++a[k]             //and increment it

   //reset all the lower index numbers, to their lowest possible value 1.
   j=k-1;
   while(j>-1)
      a[j]=1; 
      --j;

   i=0;     //and move back to the right most digit
}

print out your total permutations whose digits equaled 28

This isn't the easiest or the fastest way of finding the answer, but it's very easy to check if your logic is going right, since it's in this "digital odometer" format.

This is a program that, when you have completed it, You should keep it around.

Even on a Sunday. <smile>

Thanks for the suggestions everybody! However I can't repeat numbers in a combination, i.e. this 155 is an invalid set of 3 for the sum 11

Here is a different approach, one that assumes 1 + 3 + 7 + 8 + 9 = 28 and 3 + 1 + 7 + 8 + 9 = 28 are considered the same solution (as only the order of the terms changes).

You have N digits that may appear at most once in the sum. (They either do not appear, or appear exactly once). Therefore, you have 2^N possible sums. You can order these sums, these proposed solutions, using a single unsigned integer, where the first bit is set if the first digit is a term in the sum, the second bit is set if the second digit is a term in the sum, and so on. Of the 2^N values, only those values that have a binary representation with exactly five bits set, and sum to 28, are solutions. This turns out to consider a rather small superset of solutions -- for nine digits, it tests only 2⁹ = 512 possible solutions.

This approach only beats my previous suggestion when 2^numbers <= numbers! / (numbers - terms)!, as otherwise the other proposed superset (based on combinations), is smaller. For example, for sums with 5 terms, this approach is more efficient if you have between 5 and 21 numbers or digits to choose from.

The following program supports up to one less digit (number) than the number of bits in an unsigned long. You supply the number of terms, the desired sum, and each number or digit (possible term in the sum) as command line parameters. The program will complain if the inputs overflow or do not otherwise make sense:

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 ./combinations, then running

Code:

./combinations 3 0  -9 -8 -7 -6 -5 -4 -3 -2 -1 1 2 3 4 5 6 7 8 9

outputs all the 32 possible combinations of three nonrepeating nonzero positive or negative decimal digits that sum to zero.

Fill this with the non-repeating numbers you want, and add the checks for sum equal to whatever you want.

The output isn't in order, but getting all combinations never was easier.

Code:

#include <stdio.h>
#include <stdlib.h>

void printIt(int *n, int max);

int main(void) {
   unsigned long long count=0;
   int n[4]={1,2,3,4};
   int i,j,temp,max=4;

   int *p=malloc((max+1)*sizeof(int));
   for(i=0;i<max+1;i++)
      p[i]=i;

   temp=0;
   i=1;
   printIt(n,max);
   count=1;
   while(i<max) {
      p[i]--;
      if(i%2==1) {
         j=p[i];
      }else {
         j=0;
      }
      temp = n[i];
      n[i] = n[j];
      n[j] = temp;
      i=1;
      printIt(n,max);
      count++;
      while(p[i]==0) {
         p[i]=i;
         i++;
      }
   }   

   printf("Enumerated Combinations: %llu \n",count);
   return 0;
}
void printIt(int *n, int max) {
   int i;
   
   for(i=0;i<max;i++) {
      printf("%d ",n[i]);
   }
   putchar('\n');
}

Originally Posted by Zze

... my main issue is how can "send" the correct vector and linked list from one recursive call to another

Basically change the vector/linked list before you call the recursive function and change it back afterwards.
When the recursive function reaches the base case, just print the result (or save it in some other variable that doesn't get changed back)

Code:

        /* change vector/list */
        recursive();
        /* change back */