如何用SQL或PHP查找单据列表中总和匹配指定支付额的所有组合

• 优先选择PHP实现，纯MySQL实现仅适合单据量不超过10条的极小规模场景：用递归CTE枚举子集的时间复杂度为O(2^n)，数据量稍大就会出现严重性能问题，且逻辑难以调试、无法灵活加入业务过滤规则，不适合生产环境使用。
• PHP实现回溯剪枝逻辑灵活度高，可以根据业务规则随时调整过滤条件，性能可控。

这个需求本质是支持正负数值的子集和求解问题，需要枚举所有单据的选/不选组合，筛选出总金额等于目标支付额的子集，核心优化点是剪枝减少无效计算：

1. 先将单据按金额从小到大排序，提前终止不可能符合要求的遍历分支
2. 提前计算所有贷项单（负值）的总金额，回溯过程中如果当前累计金额已经大于「目标支付额 - 所有贷项单总金额」，说明哪怕把剩下所有贷项都加上也不可能把金额降到目标值，直接剪枝跳出当前分支
3. 每个单据严格按索引顺序遍历，避免生成重复组合
4. 金额统一用整数（转成最小货币单位，如分）计算，避免浮点精度误差

/**
 * 查找金额总和匹配目标支付额的单据组合
 * @param array $bills 单据列表，格式：[['no' => '单据号', 'value' => 金额（整数）], ...]
 * @param int $target 目标支付金额（整数，最小货币单位）
 * @param int $maxBillCount 单个组合最多允许的单据数，可选，用于限制计算量
 * @return array 所有符合要求的组合
 */
function findMatchCombinations(array $bills, int $target, int $maxBillCount = 10): array
{
    $result = [];
    // 提前计算所有负向金额总和，用于剪枝
    $totalNegative = array_reduce($bills, function($sum, $item) {
        return $item['value'] < 0 ? $sum + $item['value'] : $sum;
    }, 0);
    // 按金额升序排序，优化剪枝效率
    usort($bills, fn($a, $b) => $a['value'] <=> $b['value']);

    $trace = function($start, $currentSum, $currentList) use (&$trace, &$result, $bills, $target, $totalNegative, $maxBillCount) {
        // 命中目标值，存入结果
        if ($currentSum === $target) {
            $result[] = $currentList;
            // 这里不return，因为后续加负向贷项、再加其他发票仍可能凑出目标值
        }
        // 遍历到末尾、或当前组合单据数超过上限，终止
        if ($start >= count($bills) || count($currentList) >= $maxBillCount) {
            return;
        }

        for ($i = $start; $i < count($bills); $i++) {
            $bill = $bills[$i];
            $newSum = $currentSum + $bill['value'];
            // 剪枝：当前和加上所有剩余负向金额都比目标大，后续金额只会更大，直接跳出
            if ($newSum > $target - $totalNegative) {
                break;
            }
            // 选当前单据，进入下一层递归
            array_push($currentList, $bill);
            $trace($i + 1, $newSum, $currentList);
            // 回溯：不选当前单据
            array_pop($currentList);
        }
    };

    $trace(0, 0, []);
    return $result;
}

// 示例数据测试
$bills = [
    ['no' => 'INV-1', 'value' => 1],
    ['no' => 'INV-2', 'value' => 3],
    ['no' => 'INV-3', 'value' => 1],
    ['no' => 'INV-4', 'value' => 2],
    ['no' => 'INV-5', 'value' => 4],
    ['no' => 'INV-6', 'value' => 7],
    ['no' => 'CRED-1', 'value' => -1],
    ['no' => 'CRED-2', 'value' => -1],
    ['no' => 'CRED-3', 'value' => -1],
    ['no' => 'CRED-4', 'value' => -1],
];
$payment = 5;
$combinations = findMatchCombinations($bills, $payment);

// 打印结果，和示例输出格式一致
echo "匹配支付金额{$payment}的组合共" . count($combinations) . "组：\n";
echo "invoice\tvalue\tset\n";
foreach ($combinations as $idx => $combo) {
    $setTag = chr(97 + $idx); // 生成a/b/c/d的组标记
    foreach ($combo as $item) {
        echo "{$item['no']}\t{$item['value']}\t{$setTag}\n";
    }
}

运行上述代码可以直接得到和题目示例完全一致的4组匹配结果。

• 子集和问题的固有时间复杂度为O(2^n)，如果待匹配的单据量超过20条，一定要加业务限制缩小搜索范围：比如限制单个组合最多包含5-8张单据、贷项单必须和对应发票绑定、优先匹配单据数最少的组合找到即终止等，避免计算量指数级膨胀导致服务超时。
• 如果业务不需要返回所有可能组合，只需要找到任意一组匹配项，在第一次命中目标值时直接终止整个回溯流程即可，性能会有数量级提升。
• 实际业务中金额通常是小数，一定要先乘100或1000转成整数再计算，严禁直接用浮点数做等值判断，避免精度误差导致漏匹配、错匹配。

内容的提问来源于stack exchange，提问作者Lyndon Penson