Return all possible combinations of numbers in an

Question

var a = [1,3,6,10,-1];
function combinations(array, n) {
}

combinations(a, 9) // should return...
[[1], [3], [6], [-1], [1,3], [1,6], [1,-1], [3,6], [3,-1], [6, -1], [10, -1], [1,3,-1], [3,6,-1], [1,6,-1], [1,3,6,-1]]

maybe i'm missing some correct answers but you get the idea. Really dying to know how to solve this!

Answer 1

Try this:

var a = [1,3,6,10,-1];
function combinations(array, n) {
    var arrayCopy = [],
        results = [];

    // duplicate the array
    for (var i in array)
        arrayCopy[i] = array[i];

    for (var i in array)
        for (var j in arrayCopy)
            if ((array[i] + arrayCopy[j]) <= n)
                results.push([array[i], arrayCopy[j]]);

    return results;
}

console.log(combinations(a, 9));

This logged:

[1, 1], [1, 3], [1, 6], [1, -1], 
[3, 1], [3, 3], [3, 6], [3, -1], 
[6, 1], [6, 3], [6, -1], 
[10, -1], 
[-1, 1], [-1, 3], [-1, 6], [-1, 10], [-1, -1]

Answer 2

Brute force O(N*2^N) solution, where N = a.length < 31.

This uses the index i as a bit field to filter the elements of a in each iteration into a sublist.

var a = [1,3,6,10,-1];

function combinations(array, n) {
    var lists = [], M = 1<<array.length;
    for( var i = 1 ; i < M ; ++i ) {
        var sublist = array.filter(function(c,k){return i>>k & 1});
        if( sublist.reduce(function(p,c){return p+c},0) <= n )
            lists.push(sublist);
    }
    return lists;
}

console.log(JSON.stringify(combinations(a,9)));

[[1],[3],[1,3],[6],[1,6],[3,6],[-1],[1,-1],[3,-1],[1,3,-1],[6,-1],[1,6,-1],[3,6,-1],[1,3,6,-1],[10,-1]]

Answer 3

edit: giving credit where due.. borrowed the bulk of this logic from this answer

var combinations = function(a,m) {
  var gc = function(a) {
    var fn = function(n, src, got, all) {
      if (n == 0) {
        if (got.length > 0) {
          all[all.length] = got;
        }
        return;
      }
      for (var j = 0; j < src.length; j++) {
        fn(n - 1, src.slice(j + 1), got.concat([src[j]]), all);
      }
      return;
    }
    var all = [];
    for (var i = 0; i < a.length; i++) {
      fn(i, a, [], all);
    }
    all.push(a);
    return all;
  }
  var c = gc(a);
  return c.filter(function(e) {
    var n = e.length;
    var sum = 0;
    while(n--)
      sum += parseFloat(e[n]) || 0;
    return sum<=m;
  },m);
}
var a = [1,3,6,10,-1];
combinations(a,9);

output

[[1], [3], [6], [-1], [1, 3], [1, 6], [1, -1], [3, 6], [3, -1], [6, -1], [10, -1], [1, 3, -1], [1, 6, -1], [3, 6, -1], [1, 3, 6, -1]]