Finding a sub-array that sums to y

[yackles]

I am doing my taxes and have a long list of fractional shares sold as a result of dividend reinvestment. In order to reconcile the sale transactions, I need to be able to assemble the fractional purchases on reinvestment with the sales. Given the volume of reinvestments, and share fractions out to four decimals, this is not trivial to do by hand. The problem simplifies to the below:

Is there a simple script to identify all elements, if any, of an array that sum to a target number?

Specifically,

Inputs:

1. arbitrarily long comma-delimited list of real numbers, x1 .. xn
2. target number, y (can be last element of input list)

Output: all sub-arrays adding to y or "NULL" if none

E.g., with y last element of input list

Input:

1, 2, 3, 4, 5, 6, 7, 8, 9, 7

Output:

7
1, 6
2, 5
3, 4
1, 2, 4

Cheers,

Mike

[JimK]

OK, first of all I believe that it is a NP-Complete problem. So for for big input there is a problem :P

But try this method:

1. Put the number to the "main array"
Put the target number to var A
Sort the input elements. [that makes a new array with the elements]

2. If the main array of numbers is NULL, then reject array C, delete the largest element of array C from the main array and continue the procedure from the beginning [see below]

3. Pick the first element in the array which has the largest size. Put it to the variable B

4. If (A-B) < 0 then "delete" the element B from the array and go to step 3

5. If (A - B) >= (size of smallest element) then keep B in an array C, delete B from the array, set A=(A-B), B= the largest element of the array and repeat step 3.

6. If (A - B) < (size of smallest element), then reject B and delete it from the array, go to the largest element of the array and repeat step 3.

5. If (A - B) = 0 , then output all the elements in array C which you keep in step 3

6. Do the above steps for all elements in array C to find other solutions to the problem, but before it delete the element you took from array C from the main array

example
array = {1,2,3,4,5,6,7,8,9,7}

1. A=7, B=9, A-B = 7-9 < 0
2. A=7, B=8, A-B= 7-8 <0
3. A=7, B=7, A-B = 7-7 = 0, C=7

(step 6 for C)
array = {1,2,3,4,5,6,8,9}
1. A=7, B=9, A-B = 7-9 < 0
2. A=7, B=8, A-B= 7-8 <0
3. A=7, B=6, A-B=7-6 = 1 >= 1, C={6}
...................


OK something like that!!!
Of course that probably has terrible time complexity, but...
Hope that I `ve helped!!!