Trying to solve using recursion without using other algorithms

The code is combining recursion (the call to helper inside helper) with iteration (the while loop inside helper). You should only be using recursion.

For each element of the array, there are two choices:

1. Skip the current element. In this case, the sum is not changed, and the next element can be used. So the recursive call is sum1 = helper(arr, len - 1, sum)
2. Use the current element. In this case, the current element is added to the sum, and the next element must be skipped. So the recursive call is sum2 = helper(arr, len - 2, sum + arr[len])

So the code looks like something this:

const maxSubsetSum = (arr) => {

    const helper = (arr, len, sum) => {
        if (len < 0) return sum
        let sum1 = helper(arr, len - 1, sum)
        let sum2 = helper(arr, len - 2, sum + arr[len])
        return Math.max(sum1, sum2)
    }

    return helper(arr, arr.length - 1, 0)
}

Your thinking is right in that you need to recurse from (n-2) once you start with a current index. But you don't seem to understand that you don't need to run through your array to get sum and then recurse. So the right way is to

• either include the current item and recurse on the remaining n-2 items or

• not include the current item and recurse on the remaining n-1 items

Lets look at those two choices:

Choice 1:

You chose to include the item at the current index. Then you recurse on the remaining n-2 items. So your maximum could be item itself without adding to any of remaining n-2 items or add to some items from n-2 items. So Math.max( arr[idx], arr[idx] + recurse(idx-2)) is the maximum for this choice. If recurse(idx-2) gives you -Infinity, you just consider the item at the current index.

Choice 2:

You didn't choose to include the item at the current index. So just recurse on the remaining n-1 items - recurse(n-1)

The final maximum is maximum from those two choices.

Code is :

const maxSubsetSum = (arr) => {
    let min = -Infinity
    const helper = (arr, idx) => {
      if ( idx < 0 ) return min
      let inc = helper(arr, idx-2)
      let notInc = helper(arr, idx-1)
      inc = inc == min ? arr[idx] : Math.max(arr[idx], arr[idx] + inc)
      return Math.max( inc, notInc )
    }
    return helper(arr, arr.length - 1)
}

console.log(maxSubsetSum([-3, -5, -7, -8, 10]))
console.log(maxSubsetSum([-3, -5, -7, -8, -10]))
console.log(maxSubsetSum([-3, 5, 7, -8, 10]))
console.log(maxSubsetSum([3, 5, 7, 8, 10]))

Output :

10
-3
17
20

• For the case where all items are negative:

In this case you can say that there are no items to combine together to get a maximum sum. If that is the requirement the result should be zero. In that case just return 0 by having 0 as the default result. Code in that case is :

const maxSubsetSum = (arr) => {
    const helper = (arr, idx) => {
      if ( idx < 0 ) return 0
      let inc = arr[idx] + helper(arr, idx-2)
      let notInc = helper(arr, idx-1)
      return Math.max( inc, notInc )
    }
    return helper(arr, arr.length - 1)
}

• With memoization:

You could memoize this solution for the indices you visited during recursion. There is only one state i.e. the index so your memo is one dimensional. Code with memo is :

const maxSubsetSum = (arr) => {
    let min = -Infinity
    let memo = new Array(arr.length).fill(min)
    const helper = (arr, idx) => {
      if ( idx < 0 ) return min
      if ( memo[idx] !== min) return memo[idx]
      let inc = helper(arr, idx-2)
      let notInc = helper(arr, idx-1)
      inc = inc == min ? arr[idx] : Math.max(arr[idx], arr[idx] + inc)
      memo[idx] = Math.max( inc, notInc )
      return memo[idx]
    }
    return helper(arr, arr.length - 1)
}

A basic version is simple enough with the obvious recursion. We either include the current value in our sum or we don't. If we do, we need to skip the next value, and then recur on the remaining values. If we don't then we need to recur on all the values after the current one. We choose the larger of these two results. That translates almost directly to code:

    const maxSubsetSum = ([n, ...ns]) => 
      n == undefined  // empty array
        ? 0
        : Math .max (n + maxSubsetSum (ns .slice (1)), maxSubsetSum (ns))

Update

That was missing a case, where our highest sum is just the number itself. That's fixed here (and in the snippets below)

const maxSubsetSum = ([n, ...ns]) => 
  n == undefined  // empty array
    ? 0
    : Math .max (n, n + maxSubsetSum (ns .slice (1)), maxSubsetSum (ns))

console.log (maxSubsetSum ([3, 5, -7, 8, 10])) //15 

But, as you note in your comments, we really might want to memoize this for performance reasons. There are several ways we could choose to do this. One option would be to turn the array we're testing in one invocation of our function into something we can use as a key in an Object or a Map. It might look like this:

const maxSubsetSum = (ns) => {
  const memo = {}
  const mss = ([n, ...ns]) => {
    const key = `${n},${ns.join(',')}`
    return n == undefined
      ?  0
    : key in memo
      ? memo [key]
    : memo [key] = Math .max (n, n + maxSubsetSum (ns .slice (1)), maxSubsetSum (ns))
  }
  return mss(ns)
}

console.log (maxSubsetSum ([3, 5, -7, 8, 10])) //15 

We could also do this with a helper function that acted on the index and memoized using the index for a key. It would be about the same level of complexity.

This is a bit ugly, however, and perhaps we can do better.

There's one issue with this sort of memoization: it only lasts for the current run. It I'm going to memoize a function, I would rather it holds that cache for any calls for the same data. That means memoization in the definition of the function. I usually do this with a reusable external memoize helper, something like this:

const memoize = (keyGen) => (fn) => {
  const cache = {}
  return (...args) => {
    const key = keyGen (...args)
    return cache[key] || (cache[key] = fn (...args))
  }
}

const maxSubsetSum = memoize (ns => ns .join (',')) (([n, ...ns]) => 
  n == undefined
    ? 0
    : Math .max (n, n + maxSubsetSum (ns .slice (1)), maxSubsetSum (ns)))

console.log (maxSubsetSum ([3, 5, -7, 8, 10])) //15

memoize takes a function that uses your arguments to generate a String key, and returns a function that accepts your function and returns a memoized version of it. It runs by calling the key generation on your input, checks whether that key is in the cache. If it is, we simply return it. If not, we call your function, store the result under that key and return it.

For this version, the key generated is simply the string created by joining the array values with ','. There are probably other equally-good options.

Note that we cannot do

const recursiveFunction = (...args) => /* some recursive body */
const memomizedFunction = memoize (someKeyGen) (recursiveFunction)

because the recursive calls in memoizedFunction would then be to the non-memoized recursiveFunction. Instead, we always have to use it like this:

const memomizedFunction = memoize (someKeyGen) ((...args) => /* some recursive body */)

But that's a small price to pay for the convenience of being able to simply wrap up the function definition with a key-generator to memoize a function.

This code was accepted:

function maxSubsetSum(A) {
  return A.reduce((_, x, i) =>
    A[i] = Math.max(A[i], A[i-1] | 0, A[i] + (A[i-2] | 0)));
}

But trying to recurse that far, (I tried submitting Scott Sauyet's last memoised example), I believe results in run-time errors since we potentially pass the recursion limit.

For fun, here's bottom-up that gets filled top-down :)

function f(A, i=0){
  if (i > A.length - 3)
    return A[i] = Math.max(A[i] | 0, A[i+1] | 0);
    
  // Fill the table
  f(A, i + 1);

  return A[i] = Math.max(A[i], A[i] + A[i+2], A[i+1]);
}

var As = [
  [3, 7, 4, 6, 5], // 13
  [2, 1, 5, 8, 4], // 11
  [3, 5, -7, 8, 10] // 15
];

for (let A of As){
  console.log('' + A);
  console.log(f(A));
}