Find sum of values in array

Question

I need to develop an algorithm that finds a specific value of the sum of some elements of an array. Ex: I have an array with 50 different values and have a given value "X".

I know that the sum of the combination of some elements of this array results in this value, what I need to know is which are the elements within this list that gives this sum. I cannot use combination algorithms because above 9 elements already gives exceeded memory limit and I have arrays much larger than this to calculate.

The code I have so far is this:

/**
 * Class Teste
 */
class Teste
{
    static $values  = array(15.92, 53.27, 244.28, 388.46, 3.14, 2.92, 18.22, 4.03);
    static $include = array();
//    static         $expected = 712.02;
    static         $expected = 297.55;
    static         $ok       = false;
    private static $_instance;

    /**
     * @return static
     */
    public static function instance()
    {
        return static::$_instance = static::$_instance ?: new static();
    }

    public function __construct()
    {
        while (!static::$ok) {
            reset(static::$include);
            static::removeItem(key(static::$include));
            static::calc();
        }
        var_export(static::sum());
    }

    public static function calc()
    {
        foreach (static::$values as $k => $v) {
            var_export(static::$include);
            if (round(static::$expected, 2) == round(static::sum(), 2)) {
                static::$ok = true;
                break;
            } else if (static::$expected > static::sum()) {
                static::addItem($k);
            }
            if (round(static::$expected, 2) < round(static::sum(), 2)) {
                static::removeItem($k);
            }
        }
    }

    public static function addItem($k)
    {
        if (!array_key_exists($k, static::$include)) {
            static::$include[$k] = round(static::$values[$k], 2);
        }
    }

    public static function removeItem($k)
    {
        unset(static::$include[$k]);
    }

    public static function sum()
    {
        return round(array_sum(static::$include), 2);
    }
}

Teste::instance();

Answer 1

Optimized solution:

I had posted a reasonable solution (can be seen in the edits history of the reply), but I ended up researching a little more about this type of combination, and I came to 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 a excellent algorithm optimized for unique combinations I found, it was possible to make code much faster and with little memory usage.

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

See working on IDEONE.

Answer 2

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 (will have my upvote).

First you take all possible combinations (disregarding order). I had done something similar before in another answer, but I did without recursion here not to burst 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 scroll through the map and see which combinations give your 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 did here accumulates combinations that can pass the value you are looking for. You can make the algorithm more efficient by counting sums while assembling combinations.

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

Edit: there’s an error in the algorithm and it doesn’t pick up all the combinations (about 20% are missing). As soon as I can fix it - or someone else can find the bug and fix it before!. Corrected!

Answer 3

This solution was the 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);