PHP实现指定数值区间内无重复排列组合的最优代码问询

问题拆解 #

先明确核心需求的关键点：

• 从给定数字列表中选取可重复使用的数字，组合出总和落在 [X, Y] 区间内的所有合法组合
• 严格排除重复排列（比如 ABB 和 BBA 视为同一组合，只保留一种）
• 输入列表最多包含200个数字，必须保证算法效率，绝对不能用暴力枚举的笨办法

核心思路 #

要解决重复排列的问题，核心是强制组合的数字按非降序选择——比如选了数字A（4）之后，后续只能选A或比A大的数字，这样就不会出现先选B再选A的情况，自然不会产生重复排列。再结合回溯+剪枝的思路，大幅砍掉无效计算：

1. 先对原始数字列表去重并升序排序：去掉重复数字（比如示例中的A和E都是4，只保留一个4即可），排序后能让后续剪枝操作更高效
2. 回溯过程中，每次选择的数字不小于上一次选的数字，从根源保证组合的唯一性
3. 双重剪枝优化：
   • 如果当前总和加上当前数字已经超过Y，直接跳过该数字（继续加只会更大）
   • 如果当前总和加上最小数字都超过Y，直接终止当前分支（再怎么加都超范围，没必要继续递归）

PHP 实现代码 #

<?php

function findValidCombinations(array $numbers, int $X, int $Y): array {
    // 步骤1：去重+升序排序，减少重复计算，为剪枝做准备
    $uniqueSorted = array_values(array_unique($numbers));
    sort($uniqueSorted);
    
    $result = [];
    $minNum = $uniqueSorted[0]; // 缓存最小数字，用于快速剪枝判断

    // 回溯递归函数：currentSum当前总和，currentPath当前组合，startIndex起始选择索引（保证非降序）
    $backtrack = function(int $currentSum, array $currentPath, int $startIndex) use ($uniqueSorted, $X, $Y, $minNum, &$result, &$backtrack) {
        // 当前总和在目标范围内，记录组合
        if ($currentSum >= $X && $currentSum <= $Y) {
            $result[] = $currentPath;
        }

        // 剪枝：当前总和加最小数字都超Y，直接终止当前分支
        if ($currentSum + $minNum > $Y) {
            return;
        }

        // 从startIndex开始遍历，保证非降序选择，避免重复排列
        for ($i = $startIndex; $i < count($uniqueSorted); $i++) {
            $num = $uniqueSorted[$i];
            $newSum = $currentSum + $num;

            // 剪枝：当前数字加进去已经超Y，后面的数字更大，直接跳出循环
            if ($newSum > $Y) {
                break;
            }

            // 递归：路径加入当前数字，下一次从i开始（允许重复选当前数字）
            $backtrack($newSum, array_merge($currentPath, [$num]), $i);
        }
    };

    // 初始调用：总和0，空路径，从索引0开始选择
    $backtrack(0, [], 0);
    
    return $result;
}

// 示例测试
$numbers = [4,6,3,5,4,1];
$X = 7;
$Y = 16;
$combinations = findValidCombinations($numbers, $X, $Y);

// 打印结果（如果需要映射回原字母，比如4对应A/E，可以自行添加映射逻辑）
foreach ($combinations as $comb) {
    echo implode('', $comb) . PHP_EOL;
}
?>

关键优化说明 #

1. 去重排序：原始列表中的重复数字会导致大量重复计算，去重后只处理一次；升序排序让我们可以在循环中提前break（当当前数字加进去超Y时，后面更大的数字肯定也超）
2. 非降序选择：通过startIndex控制每次只能从当前索引及之后选数字，彻底避免了排列重复的问题，比如只会生成ABB，不会生成BAB或BBA
3. 双重剪枝：
   • 当当前总和加最小数字都超Y时，直接终止分支，省去不必要的递归
   • 循环中如果当前数字加进去超Y，直接break，后面的数字更大，无需再遍历

这个方案的时间复杂度远低于暴力枚举，即使输入200个数字（去重后数量会大幅减少），也能高效运行。

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