-1

Possible Duplicate:
Finding all possible combinations of numbers to reach a given sum

I have to create method which from array of numbers selects numbers, which sum will be exact as required one or if such doesn't exist select the minimal greater one. What would be the algorithm of this function?

public int[] selectExactSum(int[] X, int SUM) {
}

example: numbers are: {5, 2, 8, 4, 6} and required sum is 12.

The result would be: {2, 4, 6}

If required sum is 13, the result would be:{2, 8, 4} - so, the sum would be in this case 14 - the first minimal greater one.

If Required sum is 15, the possible results would be: {5, 2, 8} or {5, 4, 6}. In this case return the one of your choice - probably the first one you get.

What would be the algorithm for custom numbers and sum?

Thanks, Simon

Community
  • 1
  • 1
simonxy
  • 9
  • 2
  • 2
    What do you think would be the approach @Simonxy. Did you think of something? – Yavar May 16 '12 at 07:33
  • 1
    Homework? If yes, please add a tag `homework` – Crazenezz May 16 '12 at 07:33
  • In the example with sum=12, there are several solutions (2,4,6 but also 8,4). Should find them all? Otherwise, are the two solutions equivalent or one is better than the other? – Paolo Tedesco May 16 '12 at 07:42
  • Interesting question. Don't see why it is practical, but might as well work with it – Eon May 16 '12 at 07:42
  • [First try to create your own algorithm and post question when you not succeeded.](http://meta.stackexchange.com/a/128572/176299) – Renatas M. May 16 '12 at 07:43
  • 1
    Why wouldn't the required sum 13 return {5, 2, 6} which actually is 13? – Guffa May 16 '12 at 07:51

3 Answers3

6

This is a generalized case of the problem called subset sum. It's an NP-complete problem, thus the best known algorithm is pseudo-polynomial. If you understand the above linked algorithm, you can deduct the modification necessary to solve your problem.

mutantacule
  • 6,913
  • 1
  • 25
  • 39
1

How about recursively?

public static int[] SelectExactSum(int[] x, int sum) {
  int[]
    rest = x.Skip(1).ToArray(),
    with = x.Length == 1 ? x : x.Take(1).Concat(SelectExactSum(rest, sum - x[0])).ToArray(),
    without = x.Length == 1 ? new int[0] : SelectExactSum(rest, sum);
  int withSum = with.Sum(), withoutSum = without.Sum();
  return
    withSum >= sum ? (withoutSum >= sum ? (withSum < withoutSum ? with : without) : with) :
    withoutSum >= sum ? without : new int[0];
}

Note: Calling SelectExactSum(new int[] {5,2,8,4,6}, 13) doesn't return {2,8,4} as stated in the question, but {5,8} as that actually sums up to 13.

Guffa
  • 687,336
  • 108
  • 737
  • 1,005
  • By this way you killing the memory : `int[] rest = ..., with = ..., without = ...` and recursive calls. – Saeed Amiri May 16 '12 at 08:27
  • @SaeedAmiri: Performace becomes a problem looooong before memory does. For an array with 20 values the maximum memory usage is around 2 kb. – Guffa May 16 '12 at 08:50
0

Took me about 15 minutes to made it, you can see it running here:

http://jesuso.net/projects/selectExactSum/index.php?numbers=5%2C2%2C8%2C4%2C6&reqSum=15

And here's the code:

http://jesuso.net/projects/selectExactSum/selectExactSum.txt

I made it as simple as possible, but its made on PHP, let me know if you need some help translating it to c#.

Jesuso Ortiz
  • 133
  • 2
  • 7
  • Note*: Made it just to put you on one of the many ways to do this, of course there are "better" ways to approach this, you would still have to add error handling and stuff like that, but I kinda liked that testing it at the end you can use something like: http://jesuso.net/projects/selectExactSum/index.php?numbers=5%2C2%2C8%2C4%2C6&reqSum=105 and it still works :D So you can sum ANY number as long as you have 1 pair and 1 odd number, or just a 1 into the given numbers. – Jesuso Ortiz May 16 '12 at 08:26
  • 1
    You can post your codes in ideone.com – Saeed Amiri May 16 '12 at 08:55
  • As I read your code(I'm not php), I'm not sure if it is working. Can you explain it in JavaScript or C#? – simonxy May 16 '12 at 17:48
  • the site this answer links to is gone, it would be more useful to paste the relevant code into this answer. and yes, a c# (or python, or ruby .. ) version would be very helpful to many! – ocæon Sep 12 '20 at 03:48