PHP 输入两个整数n 和m，从数列1，2，3.......n 中随意取几个数, 使其和等于m ,要求将其中所有的可能组合列出来...

<?php
    #输入sum和n，要求输出1,2...n里所有和为sum的组合
    #这是一个可划分子问题问题
    #若用f(sum, n)表示问题的界，则元素组合共有两种情况
    #1. 和为sum的组合里包括n，则f(sum, n) = f(sum - n, n - 1)
    #2. 和为sum的组合里不包括n,则 f(sum, n) = f(sum, n - 1)
    #所以 f(sum, n) = f(sum - n, n - 1) U f(sum, n - 1)

    function combination($sum, $n, $comb) {
        if ($n < 0 || $sum < 0) {
            #当n < 0或者sum < 0都是不符合条件的结果
            // print_r($comb);
            // echo "sum: {$sum} n: {$n}<br>";
            return;
        }

        if ($sum < $n) {
            combination($sum, $sum, $comb); #sum < n，则不可能需要比sum大的数来构成组合
            return;
        }
        
        #结果求得
        if ($sum == 0) {
            #输出元素组合
            echo "Combination: ";
            foreach ($comb as $val) {
                echo $val . " ";
            }
            echo "<br>";
            return;
        }

        #组合里包含n的情况
        $comb[] = $n;
        combination($sum - $n, $n - 1, $comb);

        #组合里不包含n的情况
        array_pop($comb);
        combination($sum, $n - 1, $comb);
    }

    combination(10, 15, array());
?>