On 7/5/07, Alan Bourke <[EMAIL PROTECTED]> wrote:
> Let's say I have an array with an arbitrary number of rows, each
> containing a number.
>
> I also have a target total.
>
> Would anyone have a chunk of code already that would go through each
> combination of the numbers and output any combinations that would sum to
> the target amount?
>
> So elements 2 and 4 might equal the total, and elements 27, 98 and 143
> might as well.
>
I don't have anything premade. This could get to be pretty
computationally intensive for a lot of rows.
Are there any other constraints, a desire to use the largest numbers
(hence, the fewest items to make the target) or the smaller numbers?
Can values repeat? (If so, you can optimize them into an index). Can
you sort the rows? If so efficiencies are available. Does the order of
the rows matter?
If not, a brute force method:
For each row, add the element to each of the remaining rows, one at a time.
If you exceed the total, move on to the next element.
If you match the target, add that to the solution set.
If you are below the target, repeat the process with the remaining rows.
Bad pseudocode follows:
set = array[1,2,3,4,5,6,7,8,9,10]
rowcount = 10
solution_set = []
currentsum = 0
currentrow = 1
current values = []
target = 7 (for example)
Do FindTarget(currentrow, currentsum, target, currentvalues)
Function FindTarget(currentrow, currentsum, target, currentvalues)
for row = currentrow + 1 to rowcount
do case
case currentsum + array[row] = target
* add currentvalues and array[row] to solution_set
case currentsum + array[row] > target
* if the array is sorted ascending., no further values
need be tested.
* if the array is random, you need to continue to the last row
case currentsum+ array[row] < target
* Can add additional values:
* Add array[row] to the array of currentvalues
currentsum = currentsum + array[row]
currentrow = row
do FindTarget(currentrow, currentsum, target, currentvalues)
-- endcase
endfor
endfunc
Ted Roche
Ted Roche & Associates, LLC
http://www.tedroche.com
_______________________________________________
Post Messages to: [email protected]
Subscription Maintenance: http://leafe.com/mailman/listinfo/profox
OT-free version of this list: http://leafe.com/mailman/listinfo/profoxtech
Searchable Archive: http://leafe.com/archives/search/profox
This message: http://leafe.com/archives/byMID/profox/[EMAIL PROTECTED]
** All postings, unless explicitly stated otherwise, are the opinions of the
author, and do not constitute legal or medical advice. This statement is added
to the messages for those lawyers who are too stupid to see the obvious.
