Does Array Contain Numbers that Add up to Given Sum

Hello - what is the correct procedure to find out if a given array of X size has a specific number in it or if the sum of any amount of the array numbers adds up to a specific number?

Say you have an array of [2, 6, 1, 4] and you want to find out if the number 6 is in the array or any sum of numbers adds up to 6.

So, both index 1 (which is a 6) is correct and index 0 + index 3 (which is 2 + 4) is correct.

Nevermind - I think I have it figured out by using nested For loops and testing the sum of array.at(index) for the various loops. Seems to be working.

I think you'd have to try every single combination to do this, which can add up a lot:

In you exemple [A, B, C, D] for a value Z, you have to compare I think 16 sums, there may be a way to do it (like excluding some of them if they cannot work, for exemple if the sum of all positives values cannot reach the number or above it, then no sum will be able to), but the basic concept is this I think. I hope there is an easier way

you could maybe try a repeat loop (16 times):

compare Z = A*((int(loopindex/8))%2) + B*((int(loopindex/4))%2) + C*((int(loopindex/2))%2) + D*(loopindex%2)

intested but this should try all the sums, (it will also compare Z to 0 the first time)

EDIT: glad you figured it out, I should have though of using not only one loop though.

Aphrodite - I think my "solution" is a work in progress, as it doesn't work 100% of time when I'm testing. I'm still trouble-shooting, so i appreciate anyone else's thoughts or solutions. Thanks.

Currently I have made a function that'll return the number of sum that give the wanted result (except if the value wanted is 0):

of course now the thing is instead of returning number_of_sum, it should return a string corresponding to what we want, and to consider the 0, I'm working on that (also I think getbit makes it so you cannot make it work on an array > 32 in width, of course we can still use other techniques I think)

Aphrodite I like that algo you found there. Inspired I found a way to extend it beyond 32 elements. The idea is to use another array of 1's and 0's instead of just a number, and update the array with a simple function to add 1 in binary.

https://dl.dropboxusercontent.com/u/542 ... count.capx

It looks like counting sums of zero works, but it's also counting the case of none of the numbers added together. That case could be discarded by not using it when loopindex=0.

Edit:

Under further tests something seems broken with my capx.

Edit2:

Fixed

Aphrodite I like that algo you found there. Inspired I found a way to extend it beyond 32 elements. The idea is to use another array of 1's and 0's instead of just a number, and update the array with a simple function to add 1 in binary.

https://dl.dropboxusercontent.com/u/542 ... count.capx

It looks like counting sums of zero works, but it's also counting the case of none of the numbers added together. That case could be discarded by not using it when loopindex=0.

Edit:

Under further tests something seems broken with my capx.

R0J0hound

I didn't fully understood the capx (didn't had much time to look at it today), but instead of using an array of 0 and 1, why not taking int(Array.CurX/(2^loopindex))%2 instead of the getbit, I think it does the job over 32 elements(unless I got my math wrong).

Also by adding a condition "loopindex > 0" at your 11 event, it does not add the empty case for 0.

EDIT: Tried with 9, indeed not all solutions are found

Edit2: I begin to see the concept, your bits array help to choose the values to show it seems, I'm still strugling to understand why no all values are counted though

Ok, found the issue. I was looping with width^2 instead of 2^width. Now it gives all results. The bits array works much like getbit but can use many more than just 32 bits. Other than that it works the same way as yours.

Edit:

While it's true that you can bypass the getbit expression to access some more bits you'll run into issues once you exceed the number of significant digits in floating point numbers.