3
\$\begingroup\$

Given an array a, check to see if z numbers inside a total up to n.

If a = [1,2,3], n=3 and z=2, then this function should return true, since z numbers in that array combine to equal n.

I recently took a test for a job to fill out this function, and this was my answer. It was presumably rejected by the robots for being too slow, since one of the tests terminated with a timeout error.

var isSumPossible = function isSumPossible(a, n, z) {
  return +a.some(function (val, ix) {
    return z === 1 ? val === n : isSumPossible(a.slice(ix - 1, ix).concat(a.slice(ix + 1)), n - val, z - 1);
  });
};

How can this code be optimized to make it faster?

\$\endgroup\$
0

2 Answers 2

1
\$\begingroup\$

There's two main problems performance-wise with your solution.

  1. You examine identical subsets of the array multiple times. For example, given the array [1, 2, 3, 4, 5] with n = 7 and z = 3, you will examine (and reject) all of [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1]. Since addition is commutative, the order doesn't matter, so you're examining z! (in this case, z! = 3! = 6) more possibilities than necessary.

    The most obvious fix (to me) for this problem is to sort the array first and only inspect combinations in nondecreasing order.

  2. Doing the slice operation repeatedly performs lots of unnecessary small copies of the array. Instead of making so many copies, you can just keep track of the index of where you want to slice.

Here's an solution that directly addresses both of these issues:

var isSumPossible = function(a, n, z) {
  function f(i, n, z) {
    if(z === 0) return n === 0;
    while(i < a.length) {
      if(f(i + 1, n - a[i], z - 1)) {
        return true;
      }
      i++;
    }
    return false;
  }
  a.sort();
  return f(0, n, z);
}
\$\endgroup\$
1
\$\begingroup\$

Wow, that is slow! Those array concatenations will completely kill performance. The canonical solution is to make a dictionary of each possible combination of y=z/2 values, then check every combination of z-y values against the dictionary. This has complexity of (K choose (z+1)/2)).

\$\endgroup\$
1
  • \$\begingroup\$ Could you put that into code? I'm having trouble visualizing what that actually means. \$\endgroup\$
    – user33799
    Jan 13, 2016 at 23:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.