Find sum of values in array

This solution was most effective for arrays with many elements.

$notas = [
  999 => 8,
  456 => 4,
  789 => 5,
  123 => 2,
];

asort($notas);

function remove_maiores_que($total, $numeros) {
    return array_filter($numeros, function($n) use ($total) {
        return $n <= $total;
    });
}

function find_soma($total, $numeros) {
    if ($total <= 0) return array();

    // primeiro remove os numeros maiores que o total buscado
    $numeros = remove_maiores_que($total, $numeros);

    $sum = array_sum($numeros);

    // se a soma de todos elementos do array for inferior ao total, não adianta procurar
    if ($sum < $total) {
        return array();
    }

    // já achou o array
    if ($sum == $total) {
        return $numeros;
    }

    // remove o maior e procura soma do restante
    while( end($numeros) ) { // enquanto tiver numeros no array
        // remove o maior e sua respectiva chave
        $key = key($numeros);
        $n = array_pop($numeros);

        // verifica se o numero já é igual ao total
        if ($n == $total) {
            return array($key => $n);
        }

        // no array que sobrou, procura pela diferença do total e o número maior removido acima
        $sub_total = $total - $n;

        $soma = find_soma($sub_total, $numeros);

        // se a soma não for vazia, então encontrou a sub soma
        if ( ! empty($soma) ) {
            // adiciona o numero atual no final da soma e retorna
            $soma[$key] = $n;
            return $soma;
        }
    }

    // retorna array vazio indicando que não encontrou nenhuma soma
    return array();
}

find_soma(6, $notas);

Optimized solution:

I had posted a reasonable solution (can be seen in the answer history), but I ended up researching a bit more about this type of combination, and I came up with this code:

<?php
   static $values  = array( 15.92, 53.27, 244.28, 388.46, 3.14, 2.92, 18.22, 4.03 );
   static $expected = 297.55;
   static $precision = 100; /* para não ter problemas com ponto flutuante */

   $target = floor( $expected * $precision );
   $len = count( $values );
   for( $i = 1; $i < pow( 2, $len ); $i++ ) {
      $soma = 0;
      $set = array();
      for( $j = 0; $j < $len; $j++ ) {
         if( 1 << $j & $i ) {
            $set[] = $j;
            $soma += floor( $values[$j] * $precision );
         }
      }
      if( $soma == $target ) {
         // Estamos exibindo na tela apenas como demonstração. Se preferir pode armazenar.
         foreach( $set as $pos ) echo "[$pos]{$values[$pos]} ";
         echo " = $expected<br>\n";
      }
   }
?>

Thanks to an excellent algorithm optimized for unique combinations that I found, it was possible to leave the code much faster and with little memory usage.

The solutions I tried earlier blasted the IDE's 5-second timeout, even with only eight values in the array. This one is working extremely well at this time with that amount of data.

See working at IDEONE .

I've never programmed in PHP in my life. I'll leave an algorithm here in javascript - I ask someone to create a new answer by converting to PHP (it will have my upvote).

First you get all possible combinations (disregarding order). I had done something like this before in in another answer , but I did it without recursion here so I would not crash your stack;)

var ar = [1, 2, 3, 4, 5, 6, 7, 8, 9];
var resultado = {
    "1": {}
};
for (var i = 0; i < ar.length; i++) {
    resultado["1"][ar[i] + ""] = [ar[i]];
}

var tamanhoMaximo = ar.length;

for (var tamanho = 2; tamanho <= tamanhoMaximo; tamanho++) {
    var tamanhoAtual = resultado[tamanho + ""] = {};
    var tamanhoAnterior = resultado[(tamanho - 1) + ""];
    for (var chave in tamanhoAnterior) {
        var tempAr = tamanhoAnterior[chave];
        for (var i = 0; i < ar.length; i++) {
            if (tempAr.indexOf(ar[i]) == -1) {
                var novoAr = tempAr.slice();
                novoAr.push(ar[i]);
                novoAr.sort();
                tamanhoAtual[novoAr.join(",")] = novoAr;
            }
        }
    }
}
resultado;

Now just go through the map and see which combinations give their sum.

function encontraCombinacoes (mapa, procurado) {
    for (var chave in mapa) {
        for (var subchave in mapa[chave]) {
            var array = mapa[chave][subchave];
            var soma = 0;
            for (var i = 0; i < array.length; i++) {
                soma += array[i];
            }
            if (soma == procurado) {
                console.log(subchave);
            }
        }
    }
}
encontraCombinacoes(resultado, 6); // Só de exemplo

Note that you could already check the sums in the first code. What I've done here accumulates combinations that can pass the value you're looking for. You can leave the algorithm more efficient by counting the sums while assembling the combinations.

When someone converts this to PHP, I can delete this answer.

edit: has an error in the algorithm and it does not take all combinations (20% are missing). As soon as I can I can - or someone can find the error and fix it before! Fix it!