php数组中可能的解决方案的计算:如何改进我的算法

序言：

这个问题不是关于学习PHP的，也不是我计划在生产环境中使用的代码。我只是想看到并学习更好的方法来完成这项工作，就像我在方法中所做的那样。所以，请只更正我的代码，或者向我展示更好、更快或更短的解决方案。问题本身已经解决了。非常感谢。

---

问题：

几天前，一位用户在SO上问了一个问题。他的问题引起了我的注意，因为我想找到一种方法来解决他的需求。

他想得到PHP array的所有可能的键组合，其中值的总和是100，或者尽可能接近100。他给了我们一个数组的例子，我也会用它作为例子：

$array = array(25, 30, 50, 15, 20, 30);

例如，一个结果应该是[2, 4, 5]，因为50 + 20 + 30是100。

$sum = $array[2] + $array[4] + $array[5]; // = 100

我认为基本的想法应该很清楚。现在让我们来看看我的作品。。。

---

我的方法：

因此，作为一名开发人员，这个问题引起了我的注意。起初，我觉得这会很简单。只需做一些加法并检查结果。但后来我注意到有几点需要记住。。。

有很多组合需要测试。对于示例阵列，将存在多达720个（6! = 1*2*3*4*5*6 = 720）可能的排列。为了得到所有可能的组合，我想先得到数组的所有可能排列。

但这只是事实的一半。因为数组中可能有双值（，如您的示例30），我们无法获得数组值的所有可能排列，我们必须获得数组键的所有可能的排列。

因此，我使用了php食谱的pc_permut函数，并根据需要对其进行了修改。它将返回键数组中所有可能的排列。

/**
 * gets all possible permutations of $array
 * @param array $array
 * @param array $permutations
 * @return array
 */
function permutations($array, $permutations = array()) {
    if( !empty($array) ) {
        $result = array();
        for( $i = count($array) - 1; $i >= 0; --$i ) {
            $newItems = $array;
            $newPerms = $permutations;
            list($values) = array_splice($newItems, $i, 1);
            array_unshift($newPerms, $values);
            $result = array_merge($result, permutations($newItems, $newPerms));
        }
    }
    else {
        $result = array($permutations);
    }
    return $result;
}

这个函数的结果是一个多维数组，包含有序键数组中的所有排列。

Array (
    [0] => Array (
        [0] => 0
        [1] => 1
        [2] => 2
        [3] => 3
        [4] => 4
        [5] => 5
    )
    [1] => Array (
        [0] => 1
        [1] => 0
        [2] => 2
        [3] => 3
        [4] => 4
        [5] => 5
    )
    [...
)

所以，现在我有了所有的排列。计算可能的组合一点也不难。我只需要循环排列，增加总和，直到它们达到100或更高，然后返回密钥组合。

但我发现我错过了一件事。由于我得到了所有可能的排列，甚至有一些结果在列表中加倍。为了解释，这两个结果基本相同：

[2, 4, 5]; // 50 + 20 + 30 = 100
[4, 5, 2]; // 20 + 30 + 50 = 100

我最终在计算后对键进行了排序，并将它们用作结果数组中的索引。因此，可以肯定的是，每个组合在结果中只存在一次。这是我的combinations函数：

/**
 * gets all possible key combinations of $array with a sum below or equal $maxSum
 * @param array $array
 * @param integer $maxSum
 * @return array
 */
function combinations($array, $maxSum) {
    // get all permutations of the array keys
    $permutations = permutations(array_keys($array));
    $combinations = array();
    // loop all permutations
    foreach( $permutations as $keys ) {
        // create a container for each permutation to store calculation
        $current = array(
            "sum"  => 0,
            "keys" => array()
        );
        // now loop through the permutation keys
        foreach( $keys as $key ) {
            // if the addition is still between or equal $maxSum
            if( $current["sum"] + $array[$key] <= $maxSum ) {
                // increment the sum and add key to result
                $current["sum"] += $array[$key];
                $current["keys"][] = $key;
            }
        }
        // to be sure each combination only exists once in the result
        // order the keys and use them as array index
        sort($current["keys"]);
        $combinations[join("", $current["keys"])] = $current;
    }
    // remove the created key-index from array when finished
    return array_values($combinations);
}

直接执行很简单：

$array = array(25, 30, 50, 15, 20, 30);
print_r(combinations($array, 100));

结果是一个数组，包含所有组合。对于我们的示例数组，有十一种可能的组合。结果如下：

Array (
    [0] => Array (
        [sum] => 90
        [keys] => Array (
            [0] => 0
            [1] => 1
            [2] => 3
            [3] => 4
        )
    )
    [1] => Array (
        [sum] => 90
        [keys] => Array (
            [0] => 0
            [1] => 2
            [2] => 3
        )
    )
    [...

既然我写这个剧本是为了回答最初的问题，我会问自己，是否还有其他更好的方法来完成这项工作。也许有一种方法不需要排列，或者可以将相同的组合从计算或生成的数组中排除。我知道我也可以直接在permutations函数中执行计算，但这基本上是相同的工作流程。

我真的很想从你那里得到一些建议、建议或改进。我认为这有可能改进剧本，但实际上我不知道如何改进。但我相信它可以做得更简单、更直接。。。

感谢您抽出时间！：）

    selectedIndexes = {}
    sum = 100  
    aSorted = {15, 20, 25, 30, 30, 50} //starting values for the example
                                       //to clarify the following function
    aSum = {15, 35, 60, 90}
function n(aSorted, sum, selectedIndexes){
    compute aSum //precisely search in aSum for the index at which
                 //the elements are bigger than sum, and cut
    answer = (P(count(aSum))) X a(selectedIndexes) // with X being the cartesian product
    for (i=count(aSum)+1; i<=count(aSorted); i++){
        newASorted = splice(aSorted, count(aSum))
        // 1st break condition
        if(newASorted is empty) return answer
        // 2nd break condition the new sum < the first element of aSorted
        if (aSorted(i)<sum && sum-aSorted(i)>=aSorted(1)){
            answer += n(newASorted, sum-aSorted(i), push(selectedIndexes,    
            i))
        }
    }
return answer
}