4 ms·
I can't remember much of the P/NP stuff from my comp sci university days. Wouldn't this work? O(n * k)? <?php $input = array(-2, -3, 15, 14, 7, -10);
by mattm 16y ago
I can't remember much of the P/NP stuff from my comp sci university days.
Wouldn't this work? O(n * k)?
<?php
$input = array(-2, -3, 15, 14, 7, -10);
$sums = array();
foreach ($input as $val) {
$i = 0;
$count = count($sums);
foreach ($sums as $sum => $bool) {
if ($i >= ($count / 2)) {
break;
}
$sums[$sum + $val] = true;
}
$sums[$val] = true;
if (array_key_exists(0, $sums)) {
print "yes\n";
break;
}
}