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?
Check if sum can be found in array
javascript;interview questions;time limit exceeded
There's two main problems performance-wise with your solution.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.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);}