CODEWITHSUNDEEP
php
Rahul Mhatre
Rahul Mhatre

Reputation: 19

Find the subset of an array whose sum equal a given target using php

I am trying to implement a function below:

For example:

$a=array(1,10,25,50);
$number=15;
o/p : 15=1+1+1+1+1+10;

Upvotes: 1

Views: 372

Answers (2)

Bhaskar Jain
Bhaskar Jain

Reputation: 1691

Make a recursive function for this:

function getcomb($arr,$actualNum, $total=0, $combination_array = array()){
    foreach($arr as $k=>$v){ 
        if($v > $actualNum) continue;
            $shiftVal = $v;   

            if($total+$shiftVal <= $actualNum ){

                $combination_array[] = $shiftVal;
                $total += $shiftVal;
                $reminder = $actualNum-$total;
                //echo "<pre>combination_array";print_r($combination_array);
                if($reminder <= 0){
                    return $shiftVal;
                }else{
                    return $shiftVal .' + '.getcomb($arr, $actualNum,$total, $combination_array);
                }

            }
    }
}
$a=array(1,10,25,50);
rsort($a);

$number=15;
echo $str = getcomb($a, $number);

Cleck here to check output

Upvotes: 1

Enstage
Enstage

Reputation: 2126

Done:

$a=array(1,10,25,50);
rsort($a);
$number=15;
$final = [];
$remainder = $number;

foreach($a as $num) {
    do {
        if($num <= $number) {
            $final[] = $num;
            $remainder -= $num;
        }
        if($remainder == 0) break;
    } while($remainder >= $num);
}

echo $number . " = " . implode(' + ', $final);

Also this method:

$a=array(1,10,25,50);
rsort($a);
$number=15;
echo $number . " = "; 
$final = [];
foreach($a as $num) {
    if((int)($number / $num) > 0) {
        $final = array_merge($final, array_fill(0, (int)($number / $num), $num));
        $number -= (int)($number / $num) * $num;
    }
}
echo implode(' + ', $final);

Upvotes: 1

Related Questions