递归

<?php

declare(strict_types=1);

function extractList($array, &$list, $temp = array())
{
    if (count($temp) > 0 && !in_array($temp, $list)) {
        $list[] = $temp;
    }

    $size = count($array);
    for ($i = 0; $i < $size; $i++) {
        $copy = $array;
        $elem = array_splice($copy, $i, 1);

        if (count($copy) > 0) {
            $add = array_merge($temp, array($elem[0]));
            sort($add);
            extractList($copy, $list, $add);
        } else {
            $add = array_merge($temp, array($elem[0]));
            sort($add);
            if (!in_array($temp, $list)) {
                $list[] = $add;
            }
        }
    }
}


$sum   = 12;
$array = array(6, 1, 3, 11, 2, 5, 12);
$list  = array();

extractList($array, $list);

#Filter By SUM = $sum
$list = array_filter($list, function ($var) use ($sum) {
    return (array_sum($var) == $sum);
});

echo "<pre>";
print_r(array_values($list));

pow

<?php


$limit = 12;
$array = [1, 2, 5, 6, 7, 3];

// remove items 15 and 17 because they are great then $limit = 12
$array = array_filter($array, function ($var) use ($limit) {
    return ($var <= $limit);
});

rsort($array);

// the algorithm is usable if the number of elements is less than 20 (because set_time_limit)
$num = count($array);

//The total number of possible combinations
$total = pow(2, $num);

$out = array();

// algorithm from http://r.je/php-find-every-combination.html
// loop through each possible combination
for ($i = 0; $i < $total; $i++) {

    $comb = array();

    // for each combination check if each bit is set
    for ($j = 0; $j < $num; $j++) {
        // is bit $j set in $i?
        if (pow(2, $j) & $i) {
            $comb[] = $array[$j];
        }
    }

    if (array_sum($comb) == $limit) {
        $out[] = $comb;
    }
}

$array_map = array_map('count', $out);
array_multisort($array_map, SORT_ASC, $out);

$out = array_unique($out, SORT_REGULAR);

foreach ($out as $k => $result) {
   var_dump(implode(', ', $result));
}

动态规划

<?php

declare(strict_types=1);


class DpTest
{

    public static $list = [];

    public static function main()
    {
        $expectValue = 3600;                    // 目标值
        $n           = 20;                      // 数量
        self::getCouponList($n);
        self::dp($expectValue, self::$list, $n);
    }

    private static function getCouponList($n)
    {
        for ($i = 1; $i < $n; $i++) {
            self::$list[] = [
                "expDate"  => date("Y-m-d"),
                "coupon"   => $i * 100,
                "couponId" => $i,
            ];
        }
    }

    private static function dp($expectValue, $list, $n)
    {
        // 二维数组，记录结果，其中列代表的信息，是当前优惠券累加的值
        // 比如states[5][20] == true 表示决策第六张优惠券使用或是不使用， 前6张优惠券的决策结果，存在其总和为20的组合。
        $states[0][0]                  = true; // 哨兵，简化计算
        $states[0][$list[0]["coupon"]] = true;

        for ($i = 1; $i < $n; $i++) {
            for ($j = 0; $j < 3 * $expectValue; $j++) {
                if ($states[$i - 1][$j]) { // 第 i 张 券不用
                    $states[$i][$j] = true;
                }
            }

            for ($j = 0; $j < 3 * $expectValue; $j++) {
                $cow = $j + $list[$i]["coupon"];
                if ($states[$i - 1][$j] && $cow < 3 * $expectValue) { // 第 i 张 券要用
                    $states[$i][$cow] = true;
                }
            }
        }


        $flag = false;
        for ($k = $expectValue; $k < 3 * $expectValue + 1; $k++) {
            if ($states[$n - 1][$k]) {
                echo "最小值：{$k}";
                $flag = true; // 存在最小值
                break;
            }
        }

        if (!$flag) {
            return;
        }

        // 打印路径，即选了哪几张优惠券
        for ($i = $n - 1; $i >= 0; $i--) {
            $temp = $k - $list[$i]["coupon"];
            if ($temp >= 0 && $states[$i][$temp]) {
                echo $list[$i]["coupon"] . " \n";
                $k = $k - $list[$i]["coupon"];
            }
        }
    }
}

DpTest::main();