如何实现高效可扩展的嵌套数组目标和组合查找函数？

需要编写一个函数，在嵌套数组中查找所有子数组第二个元素之和等于指定目标值的组合，并返回对应子数组的第一个元素。

示例数据 #

输入数组 #

$array = [
    [6, 3],
    [7, 5],
    [9, 5],
    [12, 4],
    [61, 1],
    [62, 1],
    [63, 1],
    [84, 5],
    [85, 4],
    [127, 5]
];

目标值 #

$target = 32;

当前实现的PHP函数 #

public function findNumberCombination($array, $targetSum)
{
    $foundPairs = [];
    $n = count($array);
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            $pairSum = $array[$i][1] + $array[$j][1];
            if ($pairSum == $targetSum) {
                $foundPairs[] = [$array[$i][0], $array[$j][0]];
            } else {
                for ($k = $j + 1; $k < $n; $k++) {
                    $pairSum = $array[$i][1] + $array[$j][1] + $array[$k][1];
                    if ($pairSum == $targetSum) {
                        $foundPairs[] = [$array[$i][0], $array[$j][0], $array[$k][0]];
                    } else {
                        // continue checking larger combinations
                    }
                }
            }
        }
    }
    return $foundPairs;
}

当前代码仅能处理2个或3个元素的组合，且嵌套循环的写法在数组规模扩大时时间复杂度会急剧上升（O(n^k)，k为组合长度），无法适配大规模数据，需要更高效、可扩展的实现方案。

针对这个问题，推荐两种实用方案，分别适用于不同场景：

方案一：回溯法（通用所有组合长度） #

回溯法通过递归遍历所有可能的元素组合，同时记录当前的和与已选元素的第一个值；当和等于目标值时保存结果，若当前和超过目标值则直接剪枝停止递归，避免无效计算。

public function findCombinationBacktrack($array, $targetSum)
{
    $result = [];
    // 按第二个元素降序排序，方便提前剪枝
    usort($array, function($a, $b) {
        return $b[1] <=> $a[1];
    });
    
    $this->backtrack($array, $targetSum, 0, [], 0, $result);
    return $result;
}

private function backtrack($array, $target, $start, $current, $currentSum, &$result)
{
    if ($currentSum == $target) {
        $result[] = $current;
        return;
    }
    
    for ($i = $start; $i < count($array); $i++) {
        $remaining = $target - $currentSum;
        // 剪枝：当前元素值大于剩余需要的和，直接跳过
        if ($array[$i][1] > $remaining) {
            continue;
        }
        // 避免重复组合：当前元素与前一个元素值相同且未被选中时跳过
        if ($i > $start && $array[$i][1] == $array[$i-1][1]) {
            continue;
        }
        
        // 选择当前元素
        $current[] = $array[$i][0];
        $this->backtrack($array, $target, $i + 1, $current, $currentSum + $array[$i][1], $result);
        // 回溯，撤销选择
        array_pop($current);
    }
}

优势 #

• 支持任意长度的组合查找，无需修改代码适配不同长度
• 排序+剪枝大幅减少无效递归，效率远高于嵌套循环
• 自动去重，避免生成重复组合

方案二：动态规划（适合大规模数据） #

如果处理超大规模数组或仅需统计组合情况，可使用动态规划记录每个可能的和对应的元素组合集合：

public function findCombinationDP($array, $targetSum)
{
    // dp[$sum] 存储和为$sum的所有元素第一个值的组合
    $dp = array_fill(0, $targetSum + 1, []);
    $dp[0][] = [];
    
    foreach ($array as $item) {
        $value = $item[1];
        $num = $item[0];
        // 从后往前遍历，避免重复使用同一个元素
        for ($sum = $targetSum; $sum >= $value; $sum--) {
            foreach ($dp[$sum - $value] as $comb) {
                $newComb = $comb;
                $newComb[] = $num;
                $dp[$sum][] = $newComb;
            }
        }
    }
    
    // 过滤空组合（和为0的情况）
    return array_filter($dp[$targetSum], function($comb) {
        return !empty($comb);
    });
}

优势 #

• 时间复杂度为O(n*target)，目标值适中时效率远高于回溯法
• 适合处理大规模数组，内存占用可控（取决于目标值大小）

场景选择 #

• 小规模数组：两种方案差异不大，回溯法代码更直观
• 大规模数组且目标值适中：优先选择动态规划
• 目标值极大：回溯法的剪枝优化效果更明显

内容的提问来源于stack exchange，提问作者D .MOTAHARI