CODEWITHSUNDEEP
phpalgorithm
Jay Are
Jay Are

Reputation: 584

Finding potential combinations of numbers for a sum (given a number set to select from)

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.

Upvotes: 2

Views: 2532

Answers (2)

Jay Are
Jay Are

Reputation: 584

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);

Upvotes: 2

amit
amit

Reputation: 178471

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

Upvotes: 2

Related Questions