Finding combination of numbers that add to 20

[olaf94]

So for practice I want to create a programm in C++ that starts with an array of 10 numbers between 1 and 15 and then finds the best way to add those individual values up to 20.
So for example:

  int arr[] = {1,2,1,2,1,2,1,5,5,10}
  arr[7] + arr[8] + arr[9] == 20;

Afterwards, if it found a set that adds up to 20, it takes a few new numbers from another array made up of 30 numbers between 1 and 15 to refill the positions it just used to get the desired value.
Now rinse and repeat until there are no numbers left that add up to 20.

I tried a

for()
{ for()
   {
    for()
     {
       //check if arr[x] + arr[x+1] <=20, if true -->
       //check if result + arr[x+2] <=20, and so on.. 
     }
   }
}

loop, i tried several if-statements but i can't get the right algorithm into my head.
Can anyone give me a hint towards the right direction?

[lastchance]

olaf94 - how random is your array? I don't think that your problem is well-posed.

For example, if your array was {3,6,9,12,15,3,6,9,12,15} there is NO way of adding any combination of numbers up to 20 (because no multiple of 3 will make 20). Similarly, if your array was something like {11,12,13,14,15,11,12,13,14,15} - the sum of any two elements will exceed 20.

There are various "packing algorithms" which will come up with combinations not exceeding 20, but making their sum precisely equal to 20 would require a suitable original array.

[olaf94]

I forgot to add one thing, excuse me:
If no combination equals 20, i want to increase the desired result by 1, so search for one combination that adds up to 21, afterwards begin searching for 20 again.
Under no circumstances should the programm return results below 20.

[lastchance]

The search for combinations that add up to 20 (or whatever) looks like something you would do recursively. i.e. your routine checks first element plus combinations that add up to 20 minus first element etc., calling your search routine recursively.

Because there are different numbers of elements that might add up to 20, I don't think your 'clean' for() loops would be useful here. As there are only a finite number of elements, I think recursion is probably an appropriate method. But I haven't tried actually coding it!

In terms of code development I would probably develop slowly along the lines of:
- write a recursive routine that would spit out ALL combinations adding up to 20
- then add some means of determining the 'best' combination (depends what your criteria are)
- add the parts that would remove these from your array and replace with those from the other array.

As your arrays will vary in size, I suggest using vector<> rather than 'normal' arrays.