current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 3 down vote favorite

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?

share|improve this question
up vote 2 down vote accepted

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);
}
share|improve this answer
up vote 1 down vote

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)).

share|improve this answer
    
Could you put that into code? I'm having trouble visualizing what that actually means. – Houseman Jan 13 at 23:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.