2

I've been searching for a while to try and arrive at some sort of solution for a problem that is currently roadblocking a task I'm trying to complete. I've come across a few solutions in other programming languages that I really can't understand despite my attempts at doing so. I've also seen a lot of terminology surrounding this problem such as permutations, refactoring, subset sums, coins in a dollar, etc.

If I'm going about this the wrong way, please do feel free to let me know.

Here's the problem in a nutshell:

Given a set (array) of numbers, ex: 2, 3, 7, 14, how could I find what combinations of those numbers add up to (or equal) a specific sum, ex: 14.

An example of some of the potential combinations for the above example numbers:

3 + 3 + 3 + 3 + 2
7 + 3 + 2 + 2
7 + 7
14

Since the problem I'm trying to solve is in PHP, I'd love if there were a solution that could be offered in that language. If not, even if someone could better explain what the problem is that I'm trying to solve, and potential methods of doing so, I'd be greatly appreciative.

Or again if I might be going about this the wrong way, I'm all ears.

Jay Are
  • 584
  • 1
  • 5
  • 10
  • think by dynamic programming – advocateofnone Feb 11 '15 at 11:51
  • Are you looking for the actual combinations, or just how many of them there are? There could be exponential number of combinations, so it will grow quickly out of hand if you actually need all of them (Finding the number of them however is easier for relatively small integers) – amit Feb 11 '15 at 12:33
  • I need the actual combinations. The number set is part of a predefined set (not dynamic) and they are pretty much set as [3, 4, 5, 6, 7, 14], and the range of the variable sum will be in -most- cases between 1-30. I imagine the result sets based on these values shouldn't get too out of hand. – Jay Are Feb 11 '15 at 12:41

2 Answers2

2

To generate ALL solutions you are going to need to use some kind of backtracking, "guess" if the first number is in the solution or not, and recurse for each of the possibilities (it is needed to sum the result, or it is not).

Something like the following pseudo-code:

genResults(array, sum, currentResult):
   if (sum == 0): //stop clause, found a series summing to to correct number
         print currentResult
   else if (sum < 0): //failing stop clause, passed the required number
         return
   else if (array.length == 0): //failing stop clause, exhausted the array
         return
   else:
         //find all solutions reachable while using the first number (can use it multiple times)
         currentResult.addLast(array[0])
         genResults(array, sum - array[0], currentResult)
         //clean up
         currentResult.removeLast() 
         //find all solutions reachable while NOT using first number
         genResults(array+1, sum, currentResult)
         //in the above array+1 means the subarray starting from the 2nd element
amit
  • 175,853
  • 27
  • 231
  • 333
  • I'm not entirely clear on what the addLast and removeLast methods would be doing – Jay Are Feb 11 '15 at 13:01
  • @JayAre `currentResult` is some kind of dynamic array (vector in C++, ArrayList in Java) or a linked list - and `addLast(e)` adds the element `e` to the end of the list (appends it), `removeLast()` simply removes the last element from that same list (effectively decreasing its size by 1). – amit Feb 11 '15 at 13:03
2

Here's what I have managed to come up with thus far, based on amit's feedback and example, and some other examples. So far it appears to be working - but I'm not 100% certain.

$totals = array();
$x=0;

function getAllCombinations($ind, $denom, $n, $vals=array()){
    global $totals, $x;
    if ($n == 0){
        foreach ($vals as $key => $qty){
            for(; $qty>0; $qty--){
                $totals[$x][] = $denom[$key];
             }
        }
        $x++;
        return;
    }
    if ($ind == count($denom)) return;
    $currdenom = $denom[$ind];
    for ($i=0;$i<=($n/$currdenom);$i++){
        $vals[$ind] = $i;
        getAllCombinations($ind+1,$denom,$n-($i*$currdenom),$vals);
    }
}

$array = array(3, 5, 7, 14);
$sum = 30;

getAllCombinations(0, $array, $sum);

var_dump($totals);
Jay Are
  • 584
  • 1
  • 5
  • 10