Say I have 4 unsigned bytes and I know the sum of the values of those bytes is something arbitrary like 497. How would I go about finding the number of possible combinations of bytes that add up to 497? The fact that a byte can only hold 256 values is throwing me off.

11142724

Ok, so I just ran a brute force program to figure that out. But, I think you can solve this using some form of dynamic programming.

How many ways can 2 numbers (between 0 and 255) add up to this 497?
255+242,254+243 ... total of 255-242 = 13

How many ways can 2 numbers add up to 496? 13 + 1
...
How many ways can 2 numbers add up to 1? 2
How many ways can 2 numbers add up to 0? 1

Then use your table solve the problem as a whole.

Right now, the brute force program is good. Thanks!

Integer programming problems are generally NP-hard, and considering you're not actually optimizing the equation but simply look for the set of all solutions, I'd say simple brute force is your best bet.

First, sort the 4 unsigned bytes by value, so you have b3 ≥ b2 ≥ b1 ≥ b0. Call the target sum S. Pretend we're working in a weird number system where the basis function is f(n) = bn, and each each digit ai can only take on the values in the range [0, floor(S / bi)]. Note how we have a restriction on the number of digits (since only b0-3 are defined), and a restriction on the number of values each digits can take. This places a restriction on the number of values we can represent, giving us a bound for the brute force search. When you expand out the relevant equation you get:

a3b3 + a2b2 + a1b1 + a0b0

You then just "increment" this number represented by the digits a3a2a1a0 and count the number of times this equation sums to S. Since each digit has floor(S / bi) different values, you have an upper bound of S4/(b0b1b2b3) "numbers" to iterate over.

Now that I think about it, there are probably many ways you could optimize the search so that it isn't as "brute force". For instance, taking advantage of symmetry in cases where multiple bytes are equal, or making use of LCF's somehow.

This problem is not nearly as hard as general integer programming. A dynamic-programming solution (as incin suggested) would look like this:

Quote:Original post by Zipster[...] Thus, the answer to the OP's original example would be 498C3 + 2*(498C2) + 498C1 = 20708500 combinations.

That would be the case if the 4 numbers could be arbitrary non-negative integers. You are ignoring the fact that you can't store anything beyond 255 in a byte.

An interesting way to look at this kind of problem is through generating series. The problem is equivalent to finding the coefficient of x^497 in ((1-x^256)/(1-x))^4.

You're right, I just deleted my post because it was incorrect before I knew anyone replied, so sorry it isn't there anymore [grin] For the record, though:

Quote:Original post by myself
Ah, I misinterpreted the question. I thought the OP meant that he had four known values, and he wanted to find the number of combinations that add up to the target, i.e. implying a linear combination.

At any rate, this all boils down to a partitioning problem. If you added the restriction that none of the variables are allowed to be zero, then you have (S + 1) places to put a partition, and (B - 1) = 3 partitions (where B is the number of bytes, four in our case). Since partition order doesn't matter (because any different ordering would produce the same value distribution), the answer would simply be "(S + 1) chose (4 - 1)" combinations.

However, since we're allowing zero-valued bytes, this means that partitions can overlap. We know there are "(S + 1) chose (4 - 1)" combinations when partitions don't overlap (i.e. where all the bytes are greater than zero). Now we include all combinations where two partitions overlap. This is 2 * "(S + 1) chose (4 - 2)". Next, all the combinations where three partitions overlap - "(S + 1) choose (4 - 3)". You add these up to get a solution of (S+1)C3 + 2*((S+1)C2) + (S+1)C1. Thus, the answer to the OP's original example would be 498C3 + 2*(498C2) + 498C1 = 20708500 combinations. I haven't done the general case yet, but I'm willing to bet a pattern forms where the solution is the sum of ((B - 2)C(n - 1))*((S + 1)C(n)), for n from 1 to (B - 1).

EDIT: Bah, that's assuming that each variable has a range of [0, S].

But yeah, it does assume that each variable can at least be S. I'm still convinced there's a partition-based solution though, so I'll keep working on it... I'm thinking of starting with my previous approach, and then subtracting all combinations where there's a pair of partitions more than 255 elements apart. Basically take an interval approach.

Another interesting way of doing it (requires FFTW 3, although you can use any FFT implementation):