Check if in a set of numbers, a number n is equal to sum of its subset

Question

I have an array :

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

and a variable

$effectivePermission = 13;

I need to check whether this variable is equal to sum of any subset of the given array of numbers in an optimized way.

Subset sum doesn't seems to work for me here. Thanks

Can you post what you have tried and what way it did not work. Otherwise people will feel like they're just doing your homework for you... — Rob Baillie, Apr 07 '14 at 14:08
Are you guaranteed that the values in the array are consecutive bit values? — Charlie, Apr 07 '14 at 14:10
Are the values always going to be powers of two? Is there a chance that they are not all consecutive? Do they always start from 1? Is the array always sorted? Do you want to find out *how* the permission can be broken down, or *if* it can be broken down? How did you try to use subset sum? — Jon, Apr 07 '14 at 14:10
have a look here http://stackoverflow.com/questions/18305843/find-all-subsets-that-sum-to-a-particular-value — Christos, Apr 07 '14 at 14:17
thanks a lot.. Although to maintain uniqueness for the sums, it would have to be power of two. But i did not considered this feature of the values. — cosmoloc, Apr 07 '14 at 14:24
if you convert the effectivePermission=13 to binary you will get 1101, from 1101 you can extract the number 1,4 and 8 from the permissionVals array. Is this something like that you want? — Kunukn, Apr 07 '14 at 14:29
Thanks a lot Kunukn. Will try that approach. Sounds more optimzed — cosmoloc, Apr 07 '14 at 14:34

Casimir et Hippolyte · Accepted Answer · 2014-04-07T15:14:49.287

Assuming that $permissionVals contains always powers of 2, you can use the bit comparison:

$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';

A variant that will stop the foreach loop when the sum is reached. (useful if $permissionVals is big):

$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;

score 0 · Answer 2 · answered Apr 07 '14 at 14:27

Thanks for your replies
I tried various ways. And was finally able to get it work :

<?php   

    $gcount = 0;

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

    $needle = 33;
    $sum = 0;

    foreach ($set as $k => $v){
        $sum += $v;
    }

    function evaluate_array($s, $sum){
        $arr = array();
        $arr[0] = 0;

        foreach ($s as $k => $v) {
            for( $i = 0; $i <= $sum; $i++){
                if( isset($arr[$i]) ){
                    if( $arr[$i] != $v && $i + $v < $sum){
                        if( !isset($arr[$i + $v]) ){
                            $arr[$i + $v] = $v;
                        }
                    }
                }
            }
        }

        return $arr;
    }

    function solve($set, $sum, $needle){
        $stack = evaluate_array($set, $sum);

        while ($needle > 0){
            echo $stack[$needle] . "<br/>";
            $needle -= $stack[$needle];
        }
    }

    function brute_force($set, $needle){
        global $gcount;
        $gcount++;
        $sub = array(
            'found' => false
            , 'vals' => array()
            );

        $workset = $set;

        foreach($workset as $k => $v){
            if( $v == $needle){
                $sub['found'] = true;
                array_push($sub['vals'], $v);
                return $sub;
            }else{
                array_shift($workset);
                if( $needle - $v < 0){ return $sub; }
                $r = brute_force($workset, $needle - $v);
                if( $r['found'] ){
                    array_push($r['vals'], $v);
                    return $r;
                }
            }
        }

        return $sub;

    }

    function solve_bf($set, $needle){
        global $gcount;
        $sub = brute_force($set, $needle);
        $sum = 0;
        foreach($sub['vals'] as $k => $v){
            echo $v . "<br/>";
            $sum += $v;
        }

        echo "<br/>Sum: " . $sum;
        echo "<br/># Recursions: " . $gcount;
    }

    //solve($set, $sum, $needle);
    solve_bf($set, $needle);


?>

If $sum = 0, then no such subset exists. (Ref. : https://github.com/burento/Subset-Sum-Problem/commit/ba549a8e67d6495fdaffafcd2e51833b7b6a57d4)

Check if in a set of numbers, a number n is equal to sum of its subset

2 Answers2