AS3: adding different numbers in an array to get specific result.

Question

I got a numberArray. It contains intergers - randomised, within a specific range. I want to get a specific sum, but not for everything inside the numberArray, more of trying to sum up different amount of numbers (total of 5 only) inside the numberArray and see if it'll get the specific total required. and if not, it'll randomise another number to take over one of the numbers inside the numberArray.

What's the easiest way to do this ?

doing lots of

    if (numberArray[1] + numberArray[2] == specificNumber) 
    {
    }
    if (numberArray[1] + numberArray[3] == specificNumber)
    {
    }

etc. etc. etc. have too many lines of codes, and it seems like there are easier codes. right now i only have 5 different numbers in the array, so it's still bearable, but if the amount of numbers are higher.... ....

Answer 1

I would do something like the following:

• shuffle array
• take random amount of numbers from the array
• sum them up
• if the sum is not the total sum you want, repeat

Answer 2

hm, not sure what you want to do at the end when a "conclusion" or "no conclusion" is reached, but you could generate a Power set from your set of numbers then for each subset add up all the numbers in it to see if you get your desired sum.

(This would be a 'brute force' approach and could be slow if you have many numbers.)

Possibly useful for how to create a Power set: Calculating all of the subsets of a set of numbers

Answer 3

Reading your question like this: For your array of random integers, find a (or all) set(s) of integers that have a given sum.

This is an NP-Complete problem - i.e. there's no known algorithm that solves it efficiently.

The fastest known way is rather complex, so we'll go with a naive solution - should be good enough if you're not doing this on every frame or the input set is huge.

This should also work with 0 or negative values in the input set.

// The sum we're looking for:
var requiredSum:int              = 8;
// Our input set:
var numberArray:Array            = [1, 2, 3, 4, 5, 2, 3];
// Results will be stored here:
var resultSets:Array             = [];

// Go through all possible subset sizes.
// This allows subset sizes all the way up to the size of 
// the input set (numberArray.length).
// You can modify it to a fixed value (say, 5), of course:
for (var subsetSize:int = 1; subsetSize <= numberArray.length; subsetSize++)
{
   // We'll use the same array for all our attempts of this size:
   var subset:Array = new Array(subsetSize);
   findSum(numberArray, subset, 0, 0);
}

// Output results:
for (var i:int = 0; i < resultSets.length; i++)
{
    trace(resultSets[i].join("+"));
}

// numberArray : Our input set
// subset      : The set we're currently filling
// setIndex    : The position we're at in numberArray
// subsetIndex : The position we're at in the set we're filling
function findSum(numberArray:Array, subset:Array, setIndex:int, 
                 subsetIndex:int):void
{
   // Try every value from the input set starting from our current position, 
   // and insert the value at the current subset index:
   for (var index:int = setIndex ; index < numberArray.length; index++)
   {
      subset[subsetIndex] = numberArray[index];

      // Have we filled the subset?
      if (subsetIndex == subset.length - 1)
      {
         var sum:int = 0;
         for (var i:int = 0; i < subset.length; i++)
         {
            sum += subset[i];
         }

         if (sum == requiredSum)
         {
            // Clone the array before adding it to our results, 
            // since we'll be modifying it if we find more:
            resultSets.push(subset.concat());
         }
      }
      else
      {
         // Recursion takes care of combining our subset so far
         // with every possible value for the remaining subset indices:
         findSum(numberArray, subset, index + 1, subsetIndex + 1);
      }
   }
}

Output for the values used in the above code:

3+5
5+3
1+2+5
1+3+4
1+4+3
1+5+2
2+3+3
2+4+2
3+2+3
1+2+3+2
1+2+2+3

If we only need to know IF a sum exists, there's no need for the result set - we just return true/false, and break out of the recursive algorithm completely when a sum has been found:

var requiredSum:int   = 8;
var numberArray:Array = [1, 2, 3, 4, 5, 2, 3];

// Go through all possible subset sizes:
for (var subsetSize:int = 1; subsetSize <= numberArray.length; subsetSize++)
{
   // We'll use the same array for all our attempts of this size:
   var subset:Array = new Array(subsetSize);
   if (findSum(numberArray, subset, 0, 0))
   {
      trace("Found our sum!");
      // If we found our sum, no need to look for more sets:
      break;
   }
}

// numberArray : Our input set
// subset      : The set we're currently filling
// setIndex    : The position we're at in numberArray
// subsetIndex : The position we're at in the set we're filling
// RETURNS     : True if the required sum was found, otherwise false.
function findSum(numberArray:Array, subset:Array, setIndex:int, 
                 subsetIndex:int):Boolean
{
   // Try every value from the input set starting from our current position, 
   // and insert the value at the current subset index:
   for (var index:int = setIndex ; index < numberArray.length; index++)
   {
      subset[subsetIndex] = numberArray[index];

      // Have we filled the subset?
      if (subsetIndex == subset.length - 1)
      {
         var sum:int = 0;
         for (var i:int = 0; i < subset.length; i++)
         {
            sum += subset[i];
         }

         // Return true if we found our sum, false if not:
         return sum == requiredSum;
      }
      else
      {
         if (findSum(numberArray, subset, index + 1, subsetIndex + 1))
         {
            // If the "inner" findSum found a sum, we're done, so return
            // - otherwise stay in the loop and keep looking:
            return true;
         }
      }
   }
   // We found no subset with our required sum this time around:
   return false;
}

ETA: How this works... As mentioned, it's the naive solution - in other words, we're simply checking every single permutation of numberArray, summing each permutation, and checking if it's the sum we want.

The most complicated part is making all the permutations. The way this code does it is through recursion - i.e., the findSum() function filling a slot then calling itself to fill the next one, until all slots are filled and it can check the sum. We'll use the numberArray [1, 5, 4, 2] as an example here:

1. Go through all subset sizes in a loop - i.e., start by making all [a], then all [a,b], [a,b,c], [a,b,c,d]... etc.
2. For each subset size:
   1. Fill slot 1 of the subset...
   2. ... with each value of numberArray - [1, ?, ?], [5, ?, ?], [4, ?, ?]...
   3. If all slots in subset have been filled, check if the sum matches and skip step 4.
   4. (Recursively) call findSum to:
      1. Fill slot 2 of the subset...
      2. ... with each remaining value of numberArray - [1, 5, ?], [1, 4, ?], [1, 2, ?]
      3. If all slots in subset have been filled, check if the sum matches and skip step 4.
      4. (Recursively) call findSum to:
         1. Fill slot 3 of the subset
         2. ... with each remaining value of numberArray - [1, 5, 4], [1, 5, 2]
         3. If all slots in subset have been filled, check if the sum matches and skip step 4.
         4. (Recursively) call findSum (this goes on "forever", or until all slots are filled and we "skip step 4")
         5. Go to 2.4.4.1. to try next value for slot 3.
      5. Go to 2.4.1 to try next value for slot 2.
   5. Go to 2.1 to try next value for slot 1.

This way, we go through every permutation of size 1, 2, 3, 4...

There's more optimization that could be done here, since the code never checks that it actually has enough values left in the input set to fill the remaining slots - i.e. it does some loops and calls to findSum() that are unneeded. This is only a matter of efficiency, however - the result is still correct.