soma.php

<?php

$notas = [
  999 => 8,
  456 => 3,
  789 => 5,
  123 => 2,
]; // 8 5 3 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();
}

$expected = $notas;
test($notas, 18, $expected);
test($notas, 8, array(999 => 8));
test($notas, 5, array(789 => 5));
test($notas, 3, array(456 => 3));
test($notas, 2, array(123 => 2));
test($notas, 1, array());

test($notas, 13, array(789 => 5, 999 => 8));
test($notas, 11, array(456 => 3, 999 => 8));
test($notas, 7,  array(123 => 2, 789 => 5));

$notas = [1, 3, 5, 7, 14];

test($notas, 13,  array(0 => 1, 2 => 5, 3 => 7));
test($notas, 15,  array(0 => 1, 4 => 14));

$notas = [
    4911584 => 1592,
    4911585 => 5327,
    4911586 => 24428,
    4911587 => 38846,
    4911588 => 314,
    4911589 => 292,
    2485512 => 1822,
    2805627 => 403
];

asort($notas);

$expected = [
    4911589 => 292,
    4911588 => 314,
    2805627 => 403,
    4911584 => 1592,
    4911585 => 5327,
    4911586 => 24428,
    4911587 => 38846,
];

test($notas, 71202,  $expected);

$expected = [
    4911585 => 5327,
];

test($notas, 5327,  $expected);

$notas = array (
    'emi-14630784' => 1113,
    'emi-14630787' => 1088,
    'emi-14630793' => 1707,
    'emi-14635704' => 1443,
    'emi-14635706' => 2231,
    'emi-14635711' => 898,
    'emi-14637382' => 1800,
    'emi-14637385' => 450,
    'emi-14637395' => 1950,
    'emi-14637408' => 1564,
    'emi-14640085' => 551,
    'emi-14640087' => 849,
    'emi-14640096' => 497,
    'emi-14640098' => 497,
    'emi-14640134' => 4135,
    'emi-14645973' => 508,
    'emi-14645975' => 508,
    'emi-14645977' => 507,
    'emi-14645979' => 390,
    'emi-14645982' => 2250,
    'emi-14645987' => 4744,
    'emi-14645988' => 79000,
    'emi-14645989' => 979,
    'emi-14645999' => 817,
    'emi-14646000' => 817,
    'emi-14646001' => 1098,
    'emi-14630807' => 1356,
    'emi-14630809' => 870,
    'emi-14630844' => 585,
    'emi-14630845' => 2511,
    'emi-14630859' => 2238,
    'emi-14640136' => 1815,
    'emi-14640159' => 969,
    'emi-14640163' => 1178,
    'emi-14640169' => 1218,
    'emi-14640171' => 2278,
    'emi-14640175' => 1846,
    'emi-14640178' => 2829,
    'emi-14640180' => 2020,
    'emi-14640192' => 1998,
    'emi-14640197' => 1321,
    'emi-14640199' => 1513,
    'emi-14640201' => 1065,
    'emi-14640237' => 519,
    'emi-14640240' => 726,
    'emi-14640242' => 1118,
    'emi-14640247' => 760,
    'emi-14646068' => 2154,
    'emi-14646069' => 1431,
    'emi-14646073' => 330,
    'emi-14646078' => 417,
    'emi-14646079' => 417,
    'emi-14646080' => 417,
    'emi-14646081' => 373,
    'emi-14646088' => 1278,
    'emi-14646091' => 406,
    'emi-14646092' => 195,
    'emi-14646093' => 195,
    'emi-14646101' => 195,
    'emi-14646104' => 2270,
    'emi-14646105' => 2270,
    'emi-14646106' => 2270,
    'emi-14646109' => 2270,
    'emi-14646110' => 610,
    'emi-14646111' => 657,
    'emi-14646112' => 657,
    'emi-14646117' => 657,
    'emi-14646120' => 657,
    'emi-14640264' => 1670,
    'emi-14640267' => 3449,
    'emi-14640270' => 1198,
    'emi-14640272' => 1775,
    'emi-14640314' => 2431,
    'emi-14640322' => 1110,
    'emi-14640326' => 2281,
    'emi-14640329' => 2366,
    'emi-14640337' => 939,
    'emi-14640339' => 456,
    'emi-14646129' => 1938,
    'emi-14646130' => 1938,
    'emi-14646132' => 1938,
    'emi-14646134' => 1000,
    'emi-14646136' => 1000,
    'emi-14646138' => 1000,
    'emi-14646140' => 1000,
    'emi-14646143' => 1000,
    'emi-14646144' => 1000,
    'emi-14646146' => 936,
    'emi-14646148' => 936,
    'emi-14646165' => 936,
    'emi-14646167' => 936,
    'emi-14646169' => 936,
    'emi-14646170' => 547,
    'emi-14646174' => 473,
    'emi-14646176' => 473,
    'emi-14646178' => 1119,
    'emi-14646179' => 600,
    'emi-14646182' => 600,
    'emi-14640342' => 781,
    'emi-14640380' => 1272,
    'emi-14640383' => 1272,
    'emi-14640391' => 1360,
    'emi-14640400' => 508,
    'emi-14699319' => 459,
    'emi-14699373' => 459,
    'emi-14699377' => 459,
    'emi-14631354' => 1480,
    'emi-14631373' => 2393,
    'emi-14631375' => 6380,
    'emi-14631383' => 657,
    'emi-14631403' => 3195,
    'emi-14631406' => 656,
    'emi-14631407' => 1952,
    'emi-14634612' => 1139,
    'emi-14634613' => 2761,
    'emi-14634614' => 5042,
    'emi-14634615' => 1302,
    'emi-14634616' => 1458,
    'emi-14634617' => 1388,
    'emi-14634618' => 420,
    'emi-14634619' => 828,
    'emi-14634622' => 1480,
    'emi-14634624' => 1492,
    'emi-14634625' => 966,
    'emi-14634626' => 1242,
    'emi-14634627' => 1679,
    'emi-14634631' => 2127,
    'emi-14634632' => 3364,
    'emi-14634679' => 654,
    'emi-14634680' => 1712,
    'emi-14634681' => 1046,
    'emi-14634682' => 1793,
    'emi-14634683' => 1092,
    'emi-14634684' => 3002,
    'emi-14634685' => 582,
    'emi-14634687' => 1308,
    'emi-14634689' => 3961,
    'emi-14634690' => 670,
    'emi-14634691' => 521,
    'emi-14634692' => 1623,
    'emi-14634693' => 810,
    'emi-14634694' => 858,
    'emi-14634695' => 980,
    'emi-14634696' => 2865,
    'emi-14634722' => 3504,
    'emi-14634723' => 636,
    'emi-14634724' => 2215,
    'emi-14634725' => 1805,
    'emi-14634732' => 636,
    'emi-14634733' => 2828,
    'emi-14634738' => 3032,
    'emi-14634739' => 1024,
    'emi-14634740' => 1500,
    'emi-14634745' => 1550,
    'emi-14634747' => 1971,
    'emi-14634749' => 715,
    'emi-14634751' => 512,
    'emi-14634752' => 1172,
    'emi-14634763' => 756,
    'emi-14634768' => 1412,
    'emi-14634769' => 1481,
    'emi-14646503' => 13586,
    'emi-14646511' => 1995,
    'emi-14630053' => 2277,
    'emi-14639091' => 1564,
    'emi-14639107' => 2138,
    'emi-14639127' => 530,
    'emi-14639130' => 1875,
    'emi-14636751' => 593,
    'emi-14636777' => 912,
    'emi-14636828' => 2124,
    'emi-14636892' => 990,
    'emi-14636746' => 1132,
    'emi-14636811' => 2219,
    'emi-14636745' => 1805,
    'emi-14630148' => 1995,
    'emi-14636804' => 1204,
    'emi-14636805' => 2830,
    'emi-14630050' => 8969,
    'emi-14630674' => 750,
    'emi-14630728' => 411,
    'emi-14630763' => 3035,
    'emi-14630804' => 1373,
    'emi-14630870' => 1468,
    'emi-14631357' => 2340,
    'emi-14631364' => 1744,
    'emi-14633026' => 1100,
    'emi-14633032' => 849,
    'emi-14633033' => 1491,
    'emi-14633318' => 917,
    'emi-14646072' => 2040,
    'emi-14633621' => 1054,
    'emi-14633635' => 1007,
    'emi-14633655' => 1118,
    'emi-14633249' => 1601,
    'emi-14636808' => 5874,
    'emi-14633689' => 1298,
    'emi-14633690' => 707,
    'emi-14633692' => 3679,
    'emi-14633700' => 1974,
    'emi-14634620' => 2027,
    'emi-14634621' => 1731,
    'emi-14634623' => 1528,
    'emi-14634846' => 1823,
    'emi-14634970' => 383,
    'emi-14635053' => 1333,
    'emi-14635105' => 1240,
    'emi-14637392' => 5400,
    'emi-14636761' => 1298,
    'emi-14636784' => 2043,
    'emi-14636840' => 1200,
    'emi-14637404' => 890,
    'emi-14645978' => 390,
    'emi-14645983' => 18900,
    'emi-14645984' => 4350,
    'emi-14645985' => 4350,
    'emi-14645986' => 4350,
    'emi-14639095' => 7418,
    'emi-14636792' => 1362,
    'emi-14636793' => 3735,
    'emi-14636827' => 1168,
    'emi-14637405' => 890,
    'emi-14640094' => 497,
    'emi-14640183' => 1176,
    'emi-14640234' => 863,
    'emi-14640268' => 1731,
    'emi-14640359' => 918,
    'emi-14630152' => 1950,
    'emi-14630702' => 1183,
    'emi-14630733' => 2216,
    'emi-14630780' => 1133,
    'emi-14630799' => 1576,
    'emi-14630802' => 2538,
    'emi-14630822' => 6147,
    'emi-14630826' => 830,
    'emi-14630875' => 1564,
    'emi-14631351' => 1134,
    'emi-14631370' => 631,
    'emi-14633126' => 1621,
    'emi-14633291' => 1070,
    'emi-14633631' => 1357,
    'emi-14633657' => 1315,
    'emi-14633659' => 1507,
    'emi-14633687' => 1141,
    'emi-14633758' => 732,
    'emi-14634688' => 2400,
    'emi-14634720' => 755,
    'emi-14634721' => 1318,
    'emi-14634758' => 738,
    'emi-14634760' => 2583,
    'emi-14635087' => 189,
    'emi-14635177' => 848,
    'emi-14635193' => 602,
    'emi-14635197' => 457,
    'emi-14635199' => 777,
    'emi-14635201' => 997,
    'emi-14635450' => 1375,
    'emi-14635573' => 1484,
    'emi-14646085' => 645,
    'emi-14646089' => 406,
    'emi-14646123' => 1938,
    'emi-14646124' => 1938,
    'emi-14646180' => 600,
    'emi-14646187' => 107400,
    'emi-14640165' => 508,
    'emi-14640397' => 21250,
    'emi-14640239' => 1840,
    'emi-14640260' => 971,
    'emi-14640394' => 3109,
    'emi-14699916' => 571,
    'emi-14699960' => 1458,
    'emi-14699681' => 1499,
    'emi-14702064' => 58800,
    'emi-14699876' => 571,
    'emi-14699653' => 1499,
    'emi-14699696' => 260,
    'emi-14699700' => 260,
    'emi-14699397' => 459,
    'emi-14699583' => 1800,
    'emi-14699842' => 639,
    'emi-14699942' => 1458,
    'emi-14699984' => 1458,
    'emi-14700042' => 2040,
    'emi-14699880' => 571,
    'emi-14699885' => 571,
    'emi-14699950' => 1458,
    'emi-14700009' => 1431,
    'emi-14630474' => 1260,
    'emi-14630683' => 6800,
    'emi-14630705' => 1265,
    'emi-14630778' => 315,
    'emi-14630779' => 494,
    'emi-14700030' => 1431,
    'emi-14700054' => 2040,
    'emi-14700061' => 2040,
    'emi-14700069' => 2040,
    'emi-14701761' => 972,
    'emi-14631401' => 1759,
    'emi-14631415' => 4985,
    'emi-14631419' => 2936,
    'emi-14701818' => 1350,
    'emi-14633650' => 792,
    'emi-14635057' => 4279,
    'emi-14635106' => 478,
    'emi-14635200' => 813,
    'emi-14635447' => 1031,
    'emi-14636794' => 1432,
    'emi-14636823' => 2272,
    'emi-14636893' => 4191,
    'emi-14637388' => 1170,
    'emi-14637397' => 12000,
    'emi-14639101' => 7418,
    'emi-14639108' => 2138,
    'emi-14639109' => 2138,
    'emi-14639110' => 2138,
    'emi-14639111' => 2138,
    'emi-14639112' => 6380,
    'emi-14702079' => 1250,
    'emi-14630543' => 210,
    'emi-14630611' => 210,
    'emi-14640091' => 849,
    'emi-14640081' => 551,
    'emi-14640079' => 551,
    'emi-14640245' => 1634,
    'emi-14640345' => 1463,
    'emi-14640350' => 712,
    'emi-14640353' => 23535,
    'emi-14701848' => 708,
    'emi-14640355' => 96,
    'emi-14640358' => 2747,
    'emi-14640370' => 1996,
    'emi-14640374' => 2156,
    'emi-14640378' => 6497,
    'emi-14640385' => 3693,
    'emi-14640387' => 1944,
    'emi-14645993' => 426,
    'emi-14645994' => 426,
    'emi-14630621' => 210,
    'emi-14630624' => 210,
    'emi-14630660' => 1873,
    'emi-14630685' => 2640,
    'emi-14630686' => 2640,
    'emi-14630687' => 2640,
    'emi-14630688' => 2640,
    'emi-14630689' => 2640,
    'emi-14630691' => 2758,
    'emi-14630695' => 4545,
    'emi-14630716' => 621,
    'emi-14630719' => 1706,
    'emi-14630730' => 1175,
    'emi-14630731' => 2611,
    'emi-14630834' => 1521,
    'emi-14630841' => 1834,
    'emi-14631365' => 1597,
    'emi-14633031' => 1183,
    'emi-14633045' => 1405,
    'emi-14633118' => 1716,
    'emi-14633119' => 1388,
    'emi-14633121' => 1037,
    'emi-14633131' => 1966,
    'emi-14633132' => 879,
    'emi-14633141' => 3116,
    'emi-14633232' => 1737,
    'emi-14633294' => 579,
    'emi-14633297' => 1191,
    'emi-14633302' => 609,
    'emi-14633600' => 1918,
    'emi-14633602' => 592,
    'emi-14699993' => 1431,
    'emi-14633633' => 1007,
    'emi-14633634' => 1533,
    'emi-14633637' => 933,
    'emi-14633638' => 474,
    'emi-14633717' => 488,
    'emi-14635109' => 780,
    'emi-14645981' => 8400,
    'emi-14645995' => 426,
    'emi-14646075' => 330,
    'emi-14646076' => 330,
    'emi-14646077' => 2593,
    'emi-14646083' => 373,
    'emi-14646084' => 373,
    'emi-14646102' => 194,
    'emi-14646141' => 1000,
    'emi-14646145' => 1299,
    'emi-14701796' => 2775,
    'emi-14701802' => 4884,
    'emi-14635194' => 3314,
    'emi-14635256' => 825,
    'emi-14635257' => 764,
    'emi-14635446' => 1462,
    'emi-14635508' => 1360,
    'emi-14635526' => 1293,
    'emi-14635529' => 150,
    'emi-14635536' => 984,
    'emi-14635576' => 417,
    'emi-14635638' => 2028,
    'emi-14635639' => 1393,
    'emi-14635705' => 2114,
    'emi-14635709' => 5203,
    'emi-14635713' => 607,
    'emi-14635714' => 4197,
    'emi-14635716' => 1559,
    'emi-14635717' => 2878,
    'emi-14636818' => 2850,
    'emi-14636820' => 3538,
    'emi-14636821' => 4538,
    'emi-14636837' => 4065,
    'emi-14636838' => 1260,
    'emi-14636839' => 855,
    'emi-14636852' => 1350,
    'emi-14635523' => 1252,
    'emi-14635553' => 656,
    'emi-14635642' => 890,
    'emi-14636807' => 5790,
    'emi-14636824' => 6166,
    'emi-14636825' => 1289,
    'emi-14636826' => 1459,
    'emi-14636829' => 3243,
    'emi-14636831' => 4511,
    'emi-14636895' => 1725,
    'emi-14699406' => 600,
    'emi-14634727' => 1143,
    'emi-14634730' => 1770,
    'emi-14630620' => 210,
    'emi-14630623' => 210,
    'emi-14630657' => 1559,
    'emi-14630641' => 210,
    'emi-14630658' => 1272,
    'emi-14630670' => 3432,
    'emi-14630671' => 577,
    'emi-14630672' => 3849,
    'emi-14630673' => 1084,
    'emi-14630676' => 14471,
    'emi-14630679' => 6936,
    'emi-14630680' => 6936,
    'emi-14630681' => 6800,
    'emi-14630682' => 6800,
    'emi-14630684' => 6800,
    'emi-14630692' => 2912,
    'emi-14630696' => 4768,
    'emi-14630700' => 4768,
    'emi-14630722' => 665,
    'emi-14630740' => 3877,
    'emi-14637335' => 1200,
    'emi-14630765' => 1497,
    'emi-14630767' => 1937,
    'emi-14630769' => 14428,
    'emi-14630773' => 1158,
    'emi-14630776' => 2833,
    'emi-14630790' => 634,
    'emi-14630796' => 961,
    'emi-14630812' => 1946,
    'emi-14630817' => 1373,
    'emi-14630820' => 2726,
    'emi-14630829' => 735,
    'emi-14630831' => 948,
    'emi-14630837' => 1676,
    'emi-14630839' => 592,
    'emi-14630861' => 2093,
    'emi-14630863' => 1672,
    'emi-14630865' => 3199,
    'emi-14630866' => 2943,
    'emi-14630873' => 1923,
    'emi-14630877' => 7418,
    'emi-14631398' => 1792,
    'emi-14631409' => 310,
    'emi-14631411' => 1636,
    'emi-14631412' => 1263,
    'emi-14631417' => 3200,
    'emi-14699454' => 600,
    'emi-14699835' => 260,
    'emi-14645990' => 979,
    'emi-14645991' => 979,
    'emi-14645992' => 979,
    'emi-14646074' => 330,
    'emi-14646121' => 1938,
    'emi-14646126' => 1938,
    'emi-14646175' => 473,
    'emi-14646185' => 600,
    'emi-14646795' => 798,
    'emi-14700019' => 1431,
    'emi-14633034' => 990,
    'emi-14633036' => 1761,
    'emi-14633037' => 852,
    'emi-14633038' => 911,
    'emi-14633039' => 1565,
    'emi-14633040' => 1571,
    'emi-14633050' => 2871,
    'emi-14633120' => 1470,
    'emi-14633122' => 2771,
    'emi-14633123' => 1485,
    'emi-14633124' => 1678,
    'emi-14633125' => 887,
    'emi-14633129' => 2757,
    'emi-14633267' => 915,
    'emi-14633282' => 1352,
    'emi-14633285' => 1094,
    'emi-14640084' => 551,
    'emi-14640101' => 1130,
    'emi-14640142' => 1273,
    'emi-14640262' => 483,
    'emi-14640324' => 1041,
    'emi-14640348' => 763,
    'emi-14640395' => 2346,
    'emi-14701898' => 1787,
    'emi-14633595' => 1306,
    'emi-14633599' => 1000,
    'emi-14635034' => 3961,
    'emi-14635037' => 4598,
    'emi-14635051' => 599,
    'emi-14635065' => 807,
    'emi-14635068' => 1075,
    'emi-14635085' => 1091,
    'emi-14635086' => 1146,
    'emi-14635107' => 1029,
    'emi-14635112' => 1065,
    'emi-14635492' => 2000,
    'emi-14699462' => 2533,
    'emi-14699576' => 1800,
    'emi-14699610' => 1499,
    'emi-14701923' => 825,
    'emi-14634379' => 585,
    'emi-14699677' => 1499,
    'emi-14699937' => 1880,
    'emi-14636737' => 788,
    'emi-14636742' => 469,
    'emi-14636756' => 1469,
    'emi-14636757' => 903,
    'emi-14636760' => 1098,
    'emi-14636781' => 1669,
    'emi-14636782' => 688,
    'emi-14636785' => 3405,
    'emi-14636786' => 1155,
    'emi-14636795' => 1511,
    'emi-14636796' => 1890,
    'emi-14639096' => 7418,
    'emi-14639098' => 7418,
    'emi-14639113' => 6380,
    'emi-14639114' => 4279,
    'emi-14639115' => 4279,
    'emi-14639116' => 4279,
    'emi-14639117' => 4279,
    'emi-14639118' => 4279,
    'emi-14639122' => 4279,
    'emi-14639123' => 15501,
    'emi-14639136' => 353,
    'emi-14639137' => 7396,
    'emi-14639140' => 950,
    'emi-14630882' => 2063,
    'emi-14634609' => 509,
    'emi-14634610' => 1722,
    'emi-14634611' => 2700,
    'emi-14634628' => 1849,
    'emi-14634629' => 1319,
    'emi-14634630' => 1505,
    'emi-14634734' => 2042,
    'emi-14634735' => 1119,
    'emi-14634736' => 1500,
    'emi-14634737' => 1147,
    'emi-14634743' => 1566,
    'emi-14634746' => 740,
    'emi-14634756' => 1691,
    'emi-14634759' => 3264,
    'emi-14634761' => 1077,
    'emi-14634766' => 1212,
    'emi-14634779' => 1671,
    'emi-14634686' => 900,
    'emi-14634741' => 2854,
    'emi-14634765' => 1802,
    'emi-14634918' => 466,
    'emi-14634936' => 1608,
    'emi-14645996' => 426,
    'emi-14645997' => 817,
    'emi-14645998' => 817,
    'emi-14646082' => 373,
    'emi-14646086' => 645,
    'emi-14646087' => 645,
    'emi-14646115' => 657,
    'emi-14646172' => 547,
    'emi-14634813' => 1040,
    'emi-14634838' => 1460,
    'emi-14634841' => 1050,
    'emi-14634854' => 436,
    'emi-14634857' => 3600,
    'emi-14634859' => 2056,
    'emi-14634860' => 609,
    'emi-14636747' => 1185,
    'emi-14636748' => 860,
    'emi-14636749' => 1283,
    'emi-14636750' => 744,
    'emi-14636768' => 1268,
    'emi-14636769' => 1083,
    'emi-14636770' => 851,
    'emi-14636771' => 915,
    'emi-14636772' => 1988,
    'emi-14636773' => 1119,
    'emi-14636774' => 2100,
    'emi-14636775' => 746,
    'emi-14636776' => 1511,
    'emi-14636778' => 1186,
    'emi-14636779' => 507,
    'emi-14636797' => 1343,
    'emi-14636798' => 1242,
    'emi-14636799' => 1170,
    'emi-14636800' => 2631,
    'emi-14636801' => 6932,
    'emi-14636802' => 1207,
    'emi-14636803' => 1110,
    'emi-14636832' => 1137,
    'emi-14637406' => 890,
    'emi-14639121' => 4279,
    'emi-14639124' => 375,
    'emi-14639125' => 375,
    'emi-14639126' => 4869,
    'emi-14639128' => 530,
    'emi-14639129' => 530,
    'emi-14639135' => 353,
    'emi-14640195' => 705,
    'emi-14640235' => 9143,
    'emi-14640372' => 1004,
    'emi-14640376' => 744,
    'emi-14640389' => 1858,
    'emi-14630141' => 1404,
    'emi-14630145' => 1800,
    'emi-14634771' => 1500,
    'emi-14634772' => 2465,
    'emi-14634781' => 451,
    'emi-14634843' => 1283,
    'emi-14634849' => 1082,
    'emi-14634865' => 559,
    'emi-14634866' => 479,
    'emi-14634869' => 1416,
    'emi-14634871' => 995,
    'emi-14634875' => 657,
    'emi-14634878' => 382,
    'emi-14634884' => 1370,
    'emi-14634894' => 681,
    'emi-14633027' => 1177,
    'emi-14633028' => 5138,
    'emi-14633029' => 1420,
    'emi-14633030' => 1905,
    'emi-14633035' => 1874,
    'emi-14633041' => 2413,
    'emi-14633042' => 1503,
    'emi-14633043' => 1047,
    'emi-14633044' => 1754,
    'emi-14633046' => 885,
    'emi-14633047' => 1141,
    'emi-14633048' => 2941,
    'emi-14633049' => 1390,
    'emi-14633051' => 1679,
    'emi-14633128' => 742,
    'emi-14633130' => 764,
    'emi-14633133' => 3300,
    'emi-14633134' => 779,
    'emi-14633135' => 1548,
    'emi-14634896' => 469,
    'emi-14634898' => 576,
    'emi-14634899' => 507,
    'emi-14634900' => 989,
    'emi-14634901' => 809,
    'emi-14634903' => 416,
    'emi-14634930' => 866,
    'emi-14634939' => 1761,
    'emi-14634941' => 2154,
    'emi-14634943' => 2745,
    'emi-14634948' => 996,
    'emi-14634950' => 1706,
    'emi-14636835' => 3420,
    'emi-14640132' => 770,
    'emi-14630131' => 2250,
    'emi-14630135' => 2041,
    'emi-14633137' => 695,
    'emi-14633139' => 1548,
    'emi-14633142' => 1521,
    'emi-14633144' => 1098,
    'emi-14634979' => 1221,
    'emi-14635026' => 3612,
    'emi-14635030' => 957,
    'emi-14635032' => 2475,
    'emi-14635042' => 519,
    'emi-14635045' => 982,
    'emi-14635048' => 2092,
    'emi-14635050' => 1163,
    'emi-14635056' => 2085,
    'emi-14635058' => 839,
    'emi-14635059' => 724,
    'emi-14635061' => 1200,
    'emi-14635063' => 827,
    'emi-14636738' => 592,
    'emi-14636739' => 752,
    'emi-14636740' => 1549,
    'emi-14636741' => 1429,
    'emi-14636743' => 576,
    'emi-14636744' => 753,
    'emi-14636752' => 1018,
    'emi-14636753' => 1188,
    'emi-14636754' => 560,
    'emi-14636755' => 395,
    'emi-14636758' => 2706,
    'emi-14636759' => 1386,
    'emi-14636762' => 602,
    'emi-14636763' => 1186,
    'emi-14636764' => 2022,
    'emi-14636765' => 1146,
    'emi-14636766' => 1753,
    'emi-14636767' => 972,
    'emi-14636780' => 1222,
    'emi-14636783' => 1362,
    'emi-14636787' => 2366,
    'emi-14636788' => 2515,
    'emi-14636789' => 1273,
    'emi-14636790' => 1416,
    'emi-14636791' => 849,
    'emi-14636806' => 1394,
    'emi-14633218' => 644,
    'emi-14633219' => 1324,
    'emi-14633233' => 1379,
    'emi-14633235' => 2469,
    'emi-14633238' => 1783,
    'emi-14633250' => 1056,
    'emi-14633258' => 460,
    'emi-14633260' => 1216,
    'emi-14633262' => 730,
    'emi-14633263' => 2000,
    'emi-14633264' => 810,
    'emi-14633265' => 1570,
    'emi-14633272' => 1709,
    'emi-14633296' => 1518,
    'emi-14633299' => 1489,
    'emi-14633300' => 932,
    'emi-14635070' => 977,
    'emi-14635083' => 1627,
    'emi-14635088' => 903,
    'emi-14635089' => 1938,
    'emi-14635108' => 3014,
    'emi-14635111' => 604,
    'emi-14635114' => 1216,
    'emi-14635195' => 1333,
    'emi-14635196' => 695,
    'emi-14635202' => 14559,
    'emi-14635203' => 14655,
    'emi-14636809' => 2700,
    'emi-14636810' => 1223,
    'emi-14636812' => 3300,
    'emi-14636813' => 1254,
    'emi-14636814' => 1500,
    'emi-14636815' => 3450,
    'emi-14636816' => 1880,
    'emi-14636817' => 2739,
    'emi-14636819' => 4507,
    'emi-14636822' => 2280,
    'emi-14636830' => 2138,
    'emi-14636833' => 5409,
    'emi-14636834' => 1410,
    'emi-14636836' => 1950,
    'emi-14636841' => 1455,
    'emi-14636849' => 1481,
    'emi-14636850' => 1200,
    'emi-14636851' => 2040,
    'emi-14636853' => 1140,
    'emi-14636854' => 2550,
    'emi-14636855' => 1350,
    'emi-14636856' => 720,
    'emi-14636857' => 3750,
    'emi-14646766' => 1030,
    'emi-14633307' => 3600,
    'emi-14633308' => 2136,
    'emi-14633310' => 669,
    'emi-14633311' => 1710,
    'emi-14633314' => 1510,
    'emi-14633587' => 1321,
    'emi-14633588' => 1548,
    'emi-14633590' => 2855,
    'emi-14633592' => 998,
    'emi-14633608' => 5058,
    'emi-14633609' => 1399,
    'emi-14633616' => 1470,
    'emi-14633618' => 1364,
    'emi-14633623' => 1100,
    'emi-14635254' => 1582,
    'emi-14635255' => 1340,
    'emi-14635259' => 1912,
    'emi-14636888' => 1350,
    'emi-14636890' => 900,
    'emi-14636896' => 705,
    'emi-14633653' => 1218,
    'emi-14633684' => 1617,
    'emi-14633686' => 2341,
    'emi-14633720' => 1768,
    'emi-14633724' => 1090,
    'emi-14633734' => 1767,
    'emi-14633736' => 1314,
    'emi-14635348' => 764,
    'emi-14639092' => 1564,
    'emi-14639093' => 1564,
    'emi-14639094' => 7418,
    'emi-14639097' => 7418,
    'emi-14639099' => 7418,
    'emi-14639100' => 7418,
    'emi-14639102' => 7418,
    'emi-14639103' => 2138,
    'emi-14639104' => 2138,
    'emi-14639105' => 2138,
    'emi-14639106' => 2138,
    'emi-14639119' => 4279,
    'emi-14639120' => 4279,
    'emi-14639132' => 1875,
    'emi-14639133' => 1875,
    'emi-14639134' => 1875,
    'emi-14639138' => 950,
    'emi-14639139' => 9080,
    'emi-14639141' => 950,
    'emi-14630472' => 1260,
    'emi-14630479' => 1260,
    'emi-14630528' => 1694,
    'emi-14630535' => 210,
    'emi-14630540' => 210,
    'emi-14630546' => 210,
    'emi-14633759' => 855,
    'emi-14633760' => 1358,
    'emi-14633761' => 1188,
    'emi-14633787' => 1205,
    'emi-14635449' => 791,
    'emi-14630614' => 210,
    'emi-14630619' => 210,
    'emi-14630625' => 210,
    'emi-14635547' => 1443,
    'emi-14635548' => 1874,
    'emi-14635550' => 4193,
    'emi-14635552' => 729,
    'emi-14635555' => 696,
    'emi-14635557' => 3323,
    'emi-14635558' => 316,
    'emi-14635641' => 1595,
    'emi-14635643' => 7560,
    'emi-14637329' => 1350,
    'emi-14637332' => 1815,
    'emi-14630668' => 1537,
    'emi-14630669' => 1932,
    'emi-14630675' => 1320,
    'emi-14630677' => 32,
    'emi-14630678' => 1500,
    'emi-14630690' => 1939,
    'emi-14630694' => 7273,
    'emi-14630697' => 959,
    'emi-14630698' => 1443,
    'emi-14630699' => 6270,
    'emi-14630708' => 6648,
    'emi-14630710' => 753,
    'emi-14630712' => 1706,
    'emi-14630714' => 697,
    'emi-14630717' => 990,
    'emi-14630724' => 2100,
    'emi-14630727' => 2184,
    'emi-14630732' => 2853,
    'emi-14630735' => 3322,
    'emi-14630737' => 3382,
    'emi-14630738' => 10250,
    'emi-14630782' => 2147,
);

asort($notas);

var_dump(array_sum($notas));
var_dump(count($notas));

$start = microtime(true);
$soma = find_soma(1831229, $notas);
var_dump(microtime(true) - $start);

var_dump(array_sum($soma));
var_dump(count($soma));


function test($numeros, $total, $expected) {
    $soma = find_soma($total, $numeros);
    if ($soma == $expected) {
        echo "true $total\n";
    } else {
        var_dump($total);
        print_r($soma);
    }
}