0

This is sort of a follow up to a question I posted earlier (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...

Community
  • 1
  • 1
Paul
  • 41
  • 3
  • Given that you are allowing numbers to be repeated, do you guarantee that all numbers in the list are greater than zero? – Drew Dormann Dec 21 '09 at 21:39
  • 4
    Are you looking for combinations or permutations? That's not the same, you know ... – meriton Dec 21 '09 at 21:43
  • I'm pretty sure this is a project euler question. I've actually ran into two of this type on that site. It's a fun one to solve. – ckknight Dec 21 '09 at 22:01

2 Answers2

3

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.

moksef
  • 344
  • 1
  • 5
  • 17
Patrick Karcher
  • 22,995
  • 5
  • 52
  • 66
  • Good summary. Although from Paul's examples it seems that duplicates are allowed regardless of whether duplicates are in the set. – Drew Dormann Dec 21 '09 at 21:50
  • 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. Dec 21 '09 at 21:51
  • 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 Dec 21 '09 at 21:55
2

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.
  • 58,739
  • 8
  • 81
  • 86