PHP 如何递归算法？

Question

题目

有一个数组，由30个1~999键值组成，和为 12865，请写出计算此数组的 30 个值的方法
$arr[1]+$arr[2]+....+$arr[30]=12865

回答

如何把以下代码简化，因为 $i ~ $iN 是不确定的。如果有其他算法更好

function loopDeep($sum , $count, $min, $max)
{
    for ($i = $min; $i < $max; $i++) {
        for ($i2 = $min; $i2 < $max; $i2++) {
            for ($i3 = $min; $i3 < $max; $i3++) {
                for ($i4 = $min; $i4 < $max; $i4++) {
                    if ($i + $i2 + $i3 + $i4 == $sum) {
                        return [$i, $i2, $i3];
                    }
                }
            }
        }
    }
    
    return [];
}

---

2015-8-23 一种算法，查看分布。（by CSDN某大牛）

$r = foo(12865, 30);
echo array_sum($r), PHP_EOL; //验证总和
print_r(array_count_values($r)); //查看分布

function foo($num, $k, $min = 1, $max = 999)
{
    $res = array_fill(0, $k, 1);
    do {
        for ($i = 0; $i < $k; $i++) {
            $sum = array_sum($res);
            $t = rand(0, $max - $min);
            if ($res[$i] + $t > $max) $t = $max - $res[$i];
            if ($sum + $t > $num) $t = $num - $sum;
            $res[$i] += $t;
        }
    } while ($num > $sum);

    return $res;
}

12865
Array
(
    [222] => 2
    [589] => 1
    [127] => 1
    [538] => 1
    [268] => 1
    [444] => 1
    [922] => 1
    [537] => 1
    [211] => 1
    [17] => 1
    [848] => 1
    [800] => 1
    [893] => 1
    [274] => 1
    [499] => 1
    [45] => 1
    [660] => 1
    [686] => 1
    [968] => 1
    [491] => 1
    [355] => 1
    [849] => 1
    [857] => 1
    [322] => 1
    [217] => 1
    [1] => 4
)

Answer 1

正准备睡觉，瞬间有了思路。。。
先来个js版本的---我是前端（：

function forFn($i,$max,$sum,$sum_end,$loop_num,$loop_index,$indexArr){
    if($loop_index==$loop_num){
        if($sum==$sum_end){
console.log('///$sum:'+$sum+'/$sum_end:'+$sum_end+'/$indexArr:'+$indexArr+'/$loop_index:'+$loop_index);
        }
        return false;
    }else{
        for(var $ii=$i;$ii<=$max;$ii++){
            $indexArr[$loop_index]=$ii;
            if($indexArr[$loop_index]>($max-$loop_num+1+$loop_index)){
                break;
            }
            $sum=eval($indexArr.join("+"));
console.log('$sum:'+$sum+'/$sum_end:'+$sum_end+'/$loop_index:'+$loop_index+'/$ii:'+$ii+'/$indexArr:'+$indexArr);
            forFn($ii+1,$max,$sum,$sum_end,$loop_num,$loop_index+1,$indexArr);
        }
    }
};
function addFn($min,$max,$sum,$sum_end,$loop_num,$loop_index,$indexArr){
    for(var $i=$min;$i<=$max-$loop_num+1;$i++){
        var $loop_index=0;
        $indexArr[$loop_index]=$i;
        forFn($i+1,$max,$sum,$sum_end,$loop_num,$loop_index+1,$indexArr)
    }
}

addFn(0,999,0,12865,30,0,[])

php：

function forFn($i,$max,$sum,$sum_end,$loop_num,$loop_index,$indexArr){
    if($loop_index==$loop_num){
        if($sum==$sum_end){
echo('///$sum:'.$sum.'/$sum_end:'.$sum_end.'/$indexArr:'.$indexArr);
print_r($indexArr);
        };
        return false;
    }else{
        for($ii=$i;$ii<$max;$ii++){
            $indexArr[$loop_index]=$ii;
            if($indexArr[$loop_index]>($max-$loop_num+1+$loop_index)){
                break;
            }
            $sum=array_sum($indexArr);
            forFn($ii+1,$max,$sum,$sum_end,$loop_num,$loop_index+1,$indexArr);
        }
    }
};
function addFn($min,$max,$sum,$sum_end,$loop_num,$loop_index,$indexArr){
    for($i=$min;$i<($max-$loop_num+1);$i++){
        $loop_index=0;
        $indexArr[$loop_index]=$i;
        forFn($i+1,$max,$sum,$sum_end,$loop_num,$loop_index+1,$indexArr)
    }
}

addFn(0,999,0,12865,30,0,[])

刚刚用node跑了一下，没跑完（复杂度太大），也不知道对不对，谁跑完结果告诉我一下（：
可以睡觉去了。。。

用测试数据0，1，2，3跑了一下
[0,1,2,3]取3个数字，和为6；

addFn(0,3,0,6,3,0,[])

Answer 2

dp方案

dp, 只用一维数组节省内存, 但是题目复杂度太大... 不玩了.

public Set<List<Integer>> compute(int N, int SUM, int MAX_KEY) {
    Set<List<Integer>>[] pre = null;
    Set<List<Integer>>[] cur = new Set[SUM + 1];
    
    // one elem
    for (int i = 0; i <= MAX_KEY; i++) {
        cur[i] = new HashSet<>();
        cur[i].add(Collections.singletonList(i));
    }
    
    for (int i = 2; i <= N; i++) {
        pre = cur;
        cur = new Set[SUM + 1];
        for (int j = 0; j <= SUM; j++)
            for (int k = 0; k <= MAX_KEY; k++)
                if (j - k >= 0 && pre[j - k] != null) {
                    if (cur[j] == null)
                        cur[j] = new HashSet<>();
                    for (List<Integer> l: pre[j - k]) {
                        List<Integer> tmp = new ArrayList<>(l);
                        tmp.add(k);
                        Collections.sort(tmp);
                        cur[j].add(tmp);
                    }
                }
    }
    return cur[SUM];
}

@Test
public void test(){
    compute(30, 12865, 999);
}

dp方案2

二维数组, 太费内存

private Set<List<Integer>>[][] dp = null;
private Set<List<Integer>> res = null;

public Set<List<Integer>> compute(int N, int SUM, int MAX_KEY) {
    dp = new Set[N + 1][SUM + 1];
    for (int i = 0; i <= MAX_KEY; i++) {
        dp[1][i] = new HashSet<>();
        dp[1][i].add(Collections.singletonList(i));
    }
    for (int i = 2; i <= N; i++)
        for (int j = 0; j <= SUM; j++)
            for (int k = 0; k <= MAX_KEY; k++)
                if (j - k >= 0 && dp[i - 1][j - k] != null) {
                    if (dp[i][j] == null)
                        dp[i][j] = new HashSet<>();
                    for (List<Integer> l: dp[i - 1][j - k]) {
                        List<Integer> tmp = new ArrayList<>(l);
                        tmp.add(k);
                        dp[i][j].add(tmp);
                    }
                }
    return dp[N][SUM];
}

递归方案

Java代码. 用了一些优化提高效率, 但复杂度还是太高. 权当参考吧.

private Set<Long> failedSet = null;
private Set<List<Integer>> res = null;

public Set<List<Integer>> compute() {
    failedSet = new HashSet<>();
    res = new HashSet<>();
    computeInt(30, 12865, 999, new int[30]);
    return res;
}

private boolean computeInt(int count, int sum, int max, int[] arr) {
    if (count == 0 || sum < 0) {
        if (sum == 0){
            List<Integer> tmp = Arrays.stream(arr).sorted().boxed()
                                      .collect(Collectors.toList());
            res.add(tmp);
        }
        return sum == 0;
    }
    long key = (long)count * Integer.MAX_VALUE + sum;
    if (failedSet.contains(key))
        return false;
    boolean found = false;
    for (int i = 0; i <= max; i++) {
        arr[count - 1] = i;
        if (computeInt(count - 1, sum - i, Math.min(max, i), arr))
            found = true;
    }
    if (!found)
        failedSet.add(key);
    return found;
}

Answer 3

题目意思比较含糊，没说要所有结果还是只要一组还是搜索特定结果；
只要一组，数字可以重复的话，29个1加一个12836就可以了；
只要一组数字，数字要求不重复，随机生成29个，sum超过12865和重复数字的回退，最后一个用12865减掉前面29个值；
如果搜索给定的数组的话，直接DFS吧；
如果是求出所有可能结果，那就BFS吧。