Trying to solve using recursion without using other algorithms

Question

I am trying to get better at understanding recursion so that I can get better at implementing dynamic programming principles. I am aware this problem can be solved using Kadane's algorithm; however, I would like to solve it using recursion.

Problem statement:

Given an array of integers, find the subset of non-adjacent elements with the maximum sum. Calculate the sum of that subset.

I have written the following partial solution:

const maxSubsetSum = (arr) => {
    let max = -Infinity

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

If I had this data:

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

My algorithm calculates 13. I know it's because when I start my algorithm my (n - 2) values are calculated, but I am not accounting for other subsets that are (n-3) or more that still validate the problem statement's condition. I can't figure out the logic to account for the other values, please guide me on how I can accomplish that.

Answer 1

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

Answer 2

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