# Logic Problem -> Programming

Discussion in 'OT Technology' started by 5Gen_Prelude, Sep 21, 2006.

1. ### 5Gen_PreludeThere might not be an "I" in the word "Team", but

Joined:
Mar 14, 2000
Messages:
14,523
9
Location:
So here's the deal. We have a series of numbers on one side and we need to match them with a series of numbers on the other side. It isn't a straight match though - a combination of 1 or more numbers on the right side add up the the number on the left side. I need a systematic way of identifying which numbers on the right add up to the numbers on the left. For example:

Code:
```75 1
23
25
10
17
30
90
15
8
```
I can visually see that 25, 10, 17, 15, 8 add up to 75 but I want the computer to figure it out. The only way I can think of doing it is calculating each possible combination:

1
1 + 23
1 + 25
1 + 10
1 + 17
1 + 30
1 + 90
1 + 15
1 + 8
1 + 23 + 25
1 + 23 + 10
1 + 23 + 17
...

And then comparing the totals to the left side (75). After it's all said and done, I should end up with no sequences that match, or 1 or more that match. But I'm still trying to figure out the code to systematically calculate every single column.

Any ideas?

2. ### Nocera...

Joined:
Aug 9, 2000
Messages:
1,307
0
Location:
Long Island, NY
I would first put the list in descending order and then do some recursive calls to a search function that will avoid numbers that obviously wouldn't work (in your case, numbers like 90 that are > the target sum).

The following code returns [25, 23, 17, 10].

Code:
```def search_for_sum(target_sum, current_sum, number_list, current_list):
count = 0
for num in number_list:
count += 1
if (num + current_sum == target_sum):
current_list.append(num)
return current_list
elif (num + current_sum < target_sum):
current_list.append(num)
result = search_for_sum(target_sum, num + current_sum, number_list[count:], current_list)
if len(result) > 0:
return result
else:
current_list.pop()
return []

if __name__ == '__main__':
## sort the list in descending order
numbers = [90, 30, 25, 23, 17, 15, 10, 8, 1]

target_sum = 75

sum_components = search_for_sum(target_sum, 0, numbers, [])

print sum_components
```

3. ### Nocera...

Joined:
Aug 9, 2000
Messages:
1,307
0
Location:
Long Island, NY
Given 5Gen_Prelude's reputation, I'm pretty sure he's beyond "homework."

4. ### 5Gen_PreludeThere might not be an "I" in the word "Team", but

Joined:
Mar 14, 2000
Messages:
14,523
9
Location:
Lol - the fact that I didn't state which language I needed it in would kind of tip you off that it isn't homework related. It is work related though.

I had thought of using recursion but I've never been able to wrap my head around the programming and even worse the debugging of a recursive function. I'm going to have to look at this a bit more but thx a bunch for putting me in the right direction.

Joined:
Mar 14, 2000
Messages:
14,523