алгоритм — PHP: поиск набора чисел в базе данных, который суммирует до определенного числа

Это действительно ранняя проблема, но я постараюсь дать полное решение, которое не оптимально, но иллюстрирует полную стратегию решения вашей проблемы.

Прежде всего, вы можете сделать это всего за одну итерацию по массиву чисел без рекурсии и предварительной сортировки. Динамическое программирование — это все, что вам нужно, отслеживая все ранее возможные пути с частичной суммой. Идея чем-то похожа на описанный вами рекурсивный метод, но мы можем сделать это многократно и без предварительной сортировки.

Предполагая входной массив [84, 38, 12, 13, 17, 2, 78, 1, 1] и цель 29, мы перебираем числа следующим образом:

* 84 - too big, move on
* 38 - too big, move on
* 12 - gives us a subtarget of 29-12 = 17
subtargets:
17 (paths: 12)
* 13 - gives us a subtarget of 29-13=16
subtargets:
16 (paths: 13)
17 (paths: 12)
* 17 - is a subtarget, fulfilling the '12' path;
and gives us a subtarget of 29-17=12
subtargets:
12 (paths: 17)
16 (paths: 13)
17 (paths: 12)
solutions:
12+17
etc.

Хитрость заключается в том, что при цикле по числам мы храним таблицу поиска subTargets, которые являются числами, которые дали бы нам решение, используя одну или несколько комбинаций («путей») ранее увиденных чисел. Если новый номер является подзадачей, мы добавляем в наш список решений; если нет, то мы добавляем к существующим путям, где num<subTarget и двигаться дальше.

Быстрая и грязная PHP-функция для этого:

// Note: only positive non-zero integer values are supported
// Also, we may return duplicate addend sets where the only difference is the order
function findAddends($components, $target)
{
// A structure to hold our partial result paths
// The integer key is the sub-target and the value is an array of string representations
// of the 'paths' to get to that sub-target. E.g. for target=29
// subTargets = {
//   26: { '=3':true },
//   15: { '=12+2':true, '=13+1':true }
// }
// We are (mis)using associative arrays as HashSets
$subTargets = array();

// And our found solutions, stored as string keys to avoid duplicates (again using associative array as a HashSet)
$solutions = array();

// One loop to Rule Them All
echo 'Looping over the array of values...' . PHP_EOL;
foreach ($components as $num) {
echo 'Processing number ' . $num . '...' . PHP_EOL;

if ($num > $target) {
echo $num . ' is too large, so we skip it' . PHP_EOL;
continue;
}

if ($num == $target) {
echo $num . ' is an exact match. Adding to solutions..' . PHP_EOL;
$solutions['='.$num] = true;
continue;
}

// For every subtarget that is larger than $num we get a new 'sub-subtarget' as well
foreach ($subTargets as $subTarget => $paths) {
if ($num > $subTarget) { continue; }

if ($num == $subTarget) {
echo 'Solution(s) found for ' . $num . ' with previous sub-target. Adding to solutions..' . PHP_EOL;
foreach ($paths as $path => $bool) {
$solutions[$path . '+' . $num] = true;
}
continue;
}

// Our new 'sub-sub-target' is:
$subRemainder = $subTarget-$num;
// Add the new sub-sub-target including the 'path' of addends to get there
if ( ! isset($subTargets[$subRemainder])) { $subTargets[$subRemainder] = array(); }

// For each path to the original sub-target, we add the $num which creates a new path to the subRemainder
foreach ($paths as $path => $bool) {
$subTargets[$subRemainder][$path.'+'.$num] = true;
}
}

// Subtracting the number from our original target gives us a new sub-target
$remainder = $target - $num;

// Add the new sub-target including the 'path' of addends to get there
if ( ! isset($subTargets[$remainder])) { $subTargets[$remainder] = array(); }
$subTargets[$remainder]['='.$num] = true;
}
return $solutions;
}

Запустите код так:

$componentArr = array(84, 38, 12, 13, 17, 2, 78, 1, 1);
$addends = findAddends($componentArr, 29);

echo 'Result:'.PHP_EOL;
foreach ($addends as $addendSet => $bool) {
echo $addendSet . PHP_EOL;
}

какие выводы:

Looping over the array of values...
Processing number 84...
84 is too large, so we skip it
Processing number 38...
38 is too large, so we skip it
Processing number 12...
Processing number 13...
Processing number 17...
Solution(s) found for 17 with previous sub-target. Adding to solutions..
Processing number 2...
Processing number 78...
78 is too large, so we skip it
Processing number 1...
Processing number 1...
Solution(s) found for 1 with previous sub-target. Adding to solutions..

Result:
=12+17
=12+13+2+1+1