tags:

views:

306

answers:

2

This is sort of a follow up to a question I posted earlier (http://stackoverflow.com/questions/1940980/c-algorithm-find-least-number-of-objects-necessary), but a bit different.

Given I have the following code:

var max = 80;
var list = new[]{10,20,30,40,50, 60);

I want to generate a array containing all the possible combinations I can use those numbers in the list to get to that max number.

The array would contain, {40, 40}, {50, 30}, {40,30, 10} etc...

+2  A: 

The naive approach is to simply generate every combination of numbers possible, and see if they add up to the target number.

Needless to say, this has hideous time complexity. But it does the job for small lists.

EDIT: Actually, if you're allowing repeated numbers, this doesn't work. An alternative algorithm (which allows repeats, but not any negatives) is to basically keep adding up the highest number in the list, and then backtrack if you go over the target.

Anon.
+3  A: 

This is your homework, right? I think you need to do it. But, you'll want to iterate over all the numbers in descending order. Then recursively add each next descending number in the sequence. Each time the sum matches, note that combo, pop out, and move on. When your tentative sum takes you over the max variable, pop out of the function to the next function in the stack. If the max still hasn't been reached, successively add the next number down in the sequence. In this way you will cover ever possible sequence, with no duplicates (unless there are duplicates in the given set, in which case you would want that duplicate). It will be not too much code actually.

Patrick Karcher
Good summary. Although from Paul's examples it seems that duplicates are allowed regardless of whether duplicates are in the set.
Shmoopty
It's trivial to adjust this algorithm to allow that, though - just recurse starting at the current number rather than the next lower one. +1.
Anon.
oi, yes! Then you always need to include the currently operated-on number down to the next recursive function call. So, still simple code, but, good Lord, for large sets, that will be horrendous! For a really large set, some fancy math will be needed. Don't look at me!
Patrick Karcher