Skip to content

Instantly share code, notes, and snippets.

@lrvick
Created November 20, 2011 22:43
Show Gist options
  • Save lrvick/1381084 to your computer and use it in GitHub Desktop.
Save lrvick/1381084 to your computer and use it in GitHub Desktop.
Subset-Sum Solution in javascript
var subset_sum = function(items, target) {
var perms = [], layer = 0, depth = 4, attempts = 0, sum, perm,
ss = function(items) {
var item = items.shift();
for (i = 0; i < items.length; i++) {
attempts = attempts + 1;
if (attempts <= items.length * items.length) {
if (layer === 0) {
perm = [items[0], items[i]];
} else {
perm = perms.shift();
perm.push(items[0]);
}
sum = 0;
for(j = 0;j < perm.length; j++){
sum += perm[j];
}
perms.push(perm);
if (sum == target){
return perm;
}
} else {
if (layer < depth) {
attempts = 0;
layer = layer + 1;
} else {
return null;
}
}
}
items.push(item);
return ss(items);
}
return ss(items)
}
items = [1, 2, 3, 4, 5];
target = 15;
result = subset_sum(items, target);
console.log(result);
@cccCody
Copy link

cccCody commented Mar 25, 2015

subset_sum([1, 2], 3) // returns null

@pratikt-cuelogic
Copy link

need to optimize it brooo, dunno how 😞

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment