Subset sum with binary numbers

Question

I got X binary numbers of length Y and want to see if they add up to a specific sum K.

I did some research on dynamic solutions for subset sum problems; however, I think this specific problem presents a twist.

Adding two binary numbers with length Y and restricting the sum's length to Y will sometimes subtract 2^(Y) from the sum (if there is overflow). Since adding two binary numbers sometimes causes overflow, such as adding:

10000000000000000000000000000000000000010
10000000000000000000000000000000000000010

Will yield the sum

00000000000000000000000000000000000000100

Therefore, in some cases adding numbers will actually lower the current sum.

At the moment, I am banging my head into a wall. Any tips or pointers how to attack this specific version of the subset sum problem?

UPDATE:

There are no real limitations to what I can use. My only goal is to produce the fastest possible run-time with ~50 binary numbers of length ~40

Why does it matter how the numbers are expressed? What you have is still some version of the subset sum problem. So, what are the additional constraints here which will make it solvable faster? How many numbers can you have? — Pradhan
– Pradhan, Commented Dec 26, 2014 at 19:10
As far as I know this shouldn't matter, integers modulo a power of two are a ring instead of a field, but none of the subset sum algorithms I know about rely on the existence of multiplicative inverses. — user555045
– user555045, Commented Dec 26, 2014 at 19:13
Using a modulo 2^(Y+1) wont disrupt the standard dynamic-programming algorithm? — RasmusJ
– RasmusJ, Commented Dec 26, 2014 at 19:20
No, but it will require an array of length 2^Y (btw isn't it modulo 2^Y?) — user555045
– user555045, Commented Dec 26, 2014 at 19:23
You're correct, it is 2^Y. However, arrays of length 2^Y when Y = ~40 in my average run-case seems extreme. Is this the only solution? — RasmusJ
– RasmusJ, Commented Dec 26, 2014 at 19:32

kraskevich · Accepted Answer · 2014-12-26 19:48:03Z

2

You can use meet-in-the middle technique.

Split your initial array into to halves(with 25 numbers if there are 50 numbers in total).
For each half, generate all possible subset sums(it takes something likeO(2^n) or O(2^n * n) time). It should feasible for n = 25(n is the size of one half).
For each possible sum from the first half, check if there is an appropriate sum in the second half using hash table(using the fact that A + B = target (mod M) means B = target - A (mod M)).

answered Dec 26, 2014 at 19:48

kraskevich

18.6k4 gold badges37 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

RasmusJ Over a year ago

Wouldn't this result in O(n^2) solution which also requires O(n^2) memory? Perhaps it is the only way, but it is not any big step up from the brute solution (simply generating all possible subsets in O(n^2) time).

kraskevich Over a year ago

@RasmusJ It is O(2 ^ (n / 2)) time and memory. It is much better than O(2 ^ n).

Collectives™ on Stack Overflow

Subset sum with binary numbers

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related