Return smallest combination of array elements to total to a number

user_8600601 0
Viewed 107

I have an $array and a $number, and I want to find the smallest combination (least number of elements) of the $array's elements, which sums to the $number, but I can't figure out how to do this with PHP code.

Test cases:

$array = [
    'a' => '1',
    'b' => '3',
    'c' => '5',
    'd' => '5',
    'e' => '1',
    'f' => '2',
    'g' => '2',
];

If $number = 10, output should be 'c', 'd'

If $number = 1, output should be either 'a' or 'e'

If $number = 4, output should be either 'a', 'b' or 'b', 'e' or 'f', 'g'

If $number = 9 output should be 'a', 'b', 'c' or 'a', 'b', 'd' or 'c', 'f', 'g' etc.

How can I write this in code?

arrays php
3 Answers

Try this?

<?php
$array= array("a"=>"1", "b"=>"3", "c"=>"5", "d"=>"5", "e"=>"1", "f"=>"2", "g"=>"2");
$num = 4;
foreach ($array as $key => $value) {
    $n1 = (int) $value;
    if ($n1 === $num) {
        echo $key.'<br/>';
        break;
    }

    if ($n1 < $num) {
        $n2 = $num - $n1;
        if ($n2Key = isN2Exists("$n2", $array)) { // this probably can also be done using some PHP built-ins, but I just couldnt find the right one
            echo "$key,$n2Key <br/>";
        }
    }
}

function isN2Exists($value, $array) {
    foreach ($array as $k => $v) {
        if ($v === $value) {
            return $k;
        }
    }
    return false;
}

This wont work if you need more than 2 numbers. For example, if the number is 9, you can not produce 9 with two numbers in your array. You need a,b,c or c,f,g. If you want it that way I think best way to do is to use recursion.

Update

If you want to do it through recursion, please try the following code. This should give you the exact output you are looking for:

<?php
$array= array("a"=>"1", "b"=>"3", "c"=>"5", "d"=>"5", "e"=>"1", "f"=>"2", "g"=>"2");
$num = 9;

function getLeastNumbers($num, $array, $sum = 0, $level = '', $resultSet = [], $combination = []) {
    if ($sum > $num) {
        return false;
    }

    foreach ($array as $key => $value) {
        $n1 = (int) $value;

        if (($n1 + $sum) == $num) {

            $newCombination = $combination;
            $newCombination[] = $key;
            sort($newCombination);

            $resultSet[] = $newCombination;
        }

        $combinationToSend = $combination;
        $combinationToSend[] = $key;
        sort($combinationToSend);
        $array2 = $array;
        unset($array2[$key]);
        if ($return = getLeastNumbers($num, $array2, $n1 + $sum, "$level .", $resultSet, $combinationToSend)) {
            $resultSet = array_unique(array_merge($resultSet, $return), SORT_REGULAR);
        }
    }

    return $resultSet;
}

$list = getLeastNumbers($num, $array);

foreach($list as $item) {
    $length = count($item);
    $finalArray[$length][] = $item;
}


print_r($finalArray[min(array_keys($finalArray))]);
user_33601400

try this ( and use Recursive Algorithm ) 

  <?php
$array= array("a"=>"1", "b"=>"3", "c"=>"5", "d"=>"5", "e"=>"1", "f"=>"2","g"=>"2");$num=6;
foreach ($array as $key => $value) {
  if ($value==$num){
  echo $key."=>".$value."<br>";
  }
  echo "-----------------"."<br>";
  foreach( $array as $key1 => $value1) {
      if($key1 > $key){
          if(sumval($value,$value1)==$num){
              echo $key."=>".$key1."<br>";
          }
          elseif(sumval($value,$value1)<$num){
              $total=sumval($value,$value1);
              foreach( $array as $key2 => $value2) {
               if($key2 > $key1){
                   if(sumval($total,$value2)==$num){
                      echo $key."=>".$key1."=>".$key2."<br>";
                     } 
              }
          }
      }
  }
  }
}

function sumval($a,$b){
 return $a+$b;   
}

?>
user_17629470

You can try something like this

<?php
    $array = ["a"=>"1", "b"=>"3", "c"=>"5", "d"=>"5", "e"=>"1", "f"=>"2", "g"=>"2"];
    $new = $array; 
    $number = 19;//Change here to check all condition 
    $flag = false;
    if(array_sum($new) == $number){
      $temp = array_keys($new);
      echo implode(",",$temp);
      $flag = true;
      exit;
    }
    if($flag)
      exit;

    foreach($array as $key=>$value){
      if($value == $number){
        echo $key."\n";
        $flag = true;
        exit;
      }
    }
    if($flag)
      exit;

    foreach($array as $key=>$value){
      $new = $array;
      array_pop($new);
      foreach($new as $key2=>$value2){
        if($key!=$key2){
          if(($value + $value2) == $number){
            echo "$key , $key2 \n";
            $flag = true;
            exit;
          }
        }
      }
    }
    if($flag)
      exit;  

    $new = $array;
    foreach($array as $key1=>$value1){
      foreach($array as $key=>$value){
        $new = $array;
        unset($new[$key]);
        if(array_sum($new) == $number){
          $temp = array_keys($new);
          echo implode(",",$temp);
          exit;
        }
        array_pop($new);
      }
      array_pop($array);
    }

?>

Live demo : https://eval.in/897632

user_28156350
Related