Find sum combinations of a number

Question

I want to represent a number as a sum of fixed set of 4 rows of digits -

1. The 1st row of digits can be either 7 or 0
2. The 2nd row of digits can be either 5 or 0
3. The 3rd row of digits can be either 3 or 0
4. The 4th row of digits can be either 1 or 0

Example 1 - Number "17776" can be represented as

07777
+5555
+3333
+1111

17776

Example 2 - Number "17731" can be represented as

07770
+5550
+3300
+1111

17731

Example 3 - Number "520" can be represented as

00070
+0050
+0300
+1100

520

OR

00007
+0500
+0003
+0010

520

NOTE: As in example 3 above, there can be more than 1 combination of sums for a given number. I need to find all possible combinations in that case.

What would be the fastest way to find these combinations? (The brute force approach would be to loop through all possible combinations and check againt the sum total, but that would take a long time.)

Code or pseudo-code in Java or C# is appreciated.

Thanks!

Answer 1

Actually there aren't so many combinations. $4$ digits per line, each digits can be only $2$ values, so for a line there are $$2^4 = 16$$ combinations. $4$ lines like that so, in total, there are $$16\times 16\times 16\times 16\times = 16^4 = 65536$$ combinations. Even for the computers of 1983 that would be a quick deal!

As for the algorithm, this is something in C easily translatable to Java. I'll explain how it works!

We just need to count in base $2$, and this is what computers do best...

Principle: we count from $0$ to $15$ ($0000$ to $1111$ in base $2$) for each of the $4$ lines, and for each we use a function that multiply the bit rank (from the right) by its $10^{rank}$, for each of the $4$ bits. For instance for $0010$, rank of the $1$ is $1$ (bit count starts at $0$), and for the $2^{nd}$ line (of $5s$) that would give $5\times 10^1$.

Whole example, for $0101$ and the line of $3s$ we have $10^0\times 3+10^1\times 0+10^2\times 3+10^3\times 0$.

First a function that converts a binary number (4 bits) to its $7/5/3/1$ number, and prints the number

int bin2num(int bin, int n) { // bin the binary number, n one of 7/5/3/1
     int i,tens=1,num=0;      // num resulting number, tens power of 10
     char s[5];               // string to store the number to be displayed
     s[4] = '\0';             // C strings end with 0 (start from end, here!)
     for (i=0 ; i<4 ; i++) {  // 4 bits
          if ((bin % 2) == 1) {     // if our number is odd
                num += tens * n;    // multiply n by the 10 power, add to 'num'
                s[3 - i] = n + '0'; // add it to this local sum (and add digit to string)
          }
          else {
                s[3 - i] = '0';     // otherwise, put '0' in string
          }
          tens *= 10;               // next power of 10
          bin >>= 1;                // Bit shift, right side, of bin
     }
     printf(" +%s\n", s);           // print the number
     return num;                    // return it to the caller
}

Now we call that function

 int a,b,c,d;

 for(a=0 ; a<16 ; a++) {                 // 'a' first row
      for(b=0 ; b<16 ; b++) {            // 'b' second etc...
            for(c=0 ; c<16 ; c++) {
                 for(d=0 ; d<16 ; d++) {
                      printf("New sum:\n");
                      int asum = bin2num(a, 7); 
                      int bsum = bin2num(b, 5);
                      int csum = bin2num(c, 3);
                      int dsum = bin2num(d, 1);
                      int sum = asum + bsum + csum + dsum;
                      printf("=%04d\n",sum); // Display our sum
                      if (sum == 17776) {    // Check for a specific number!
                            printf("Bingo!\n");
                      }
                 }
            }
      }
 }

Here in the function I use another $0\to 3$ loop, called $4$ times, so the time complexity is $65536 \times 16$ ... still low!

(edit: added display of sum for each combinations)