php - 检查一组数字中的数字 n 是否等于其子集的总和

Question

我有一个数组:

$permissionVals = array (1,2,4,8,16,32);

和一个变量

$effectivePermission = 13;

我需要以优化的方式检查此变量是否等于给定数字数组的任何子集的总和。

子集和在这里似乎对我不起作用。谢谢

Answer 1

假设 $permissionVals 总是包含 2 的幂，您可以使用位比较:

$permissionVals = array(1,2,4,8,16,32);
$target = 13;
$res = array();

foreach ($permissionVals as $val) {
    if ($target & $val) $res[] = $val;
}

if (array_sum($res) == $target)
    print_r($res);
else 
    echo 'the message you want';

当达到总和时将停止 foreach 循环的变体。 (如果 $permissionVals 很大，则很有用):

$sum = 0;
$message = 'the message you want';

foreach ($permissionVals as $val) {
    if ($target & $val) {
        $res[] = $val;
        $sum += $val;
    }
    if ($sum == $target) {
    $message = '';
    print_r($res);
    break;
    }
}

echo $message;