0

What I have so far

let threeSum = (array, targetSum) => {
    let newArray = []
    if (array.length === 0) {
        return newArray
    }
    for (let i = 0; i < array.length; i++) {
        const num1 = array[i];
        for (let j = i + 1; j < array.length; j++) {
            const num2 = array[j];
            for (let k = j + 1; k < array.length; k++) {
                const num3 = array[k];
                if (num1 + num2 + num3 === targetSum) {
                    newArray.push([num1, num2, num3])
                }
            }
        }
    }
    return newArray
}

console.log(threeSum([12, 3, 1, 2, -6, 5, -8, 6], 0))
//  [[-8, 2, 6], [-8, 3, 5], [-6, 1, 5]]

This works but only because I'm iterating through the array, I've tried checking the last and first number then slicing the array everytime I recall the function. I've written a base case so far but I'm lost on the recursion step.

This is what I have for the recursion:

let threeSum = (array, targetSum) => {
    let newArray = []
    if (array.length === 0) {
        return newArray
    }
    let num1 = array[0]
    let num2 = array[1]
    let num3 = array[2]
    if (num1 + num2 + num3 === targetSum) {
        newArray.push([num1, num2, num3])
    }
    return array.slice(1), targetSum
}

console.log(threeSum([12, 3, 1, 2, -6, 5, -8, 6], 0))
//  [[-8, 2, 6], [-8, 3, 5], [-6, 1, 5]]
Dylan Welzel
  • 55
  • 6
  • 1
    What about just generating all possible combinations from your array and check if their sum adds up to the target sum? There are already questions on SO with solutions that can perform the combination generation for you. – Terry Aug 15 '21 at 20:24
  • Right I think that's what I have in the first example but I'm being asked to use recursion here. – Dylan Welzel Aug 15 '21 at 20:36
  • Does this answer your question? [combinations of size N from an array](https://stackoverflow.com/questions/37075180/combinations-of-size-n-from-an-array) – ggorlen Aug 15 '21 at 21:39
  • 1
    If you're doing the 3-sum problem, see [how to calculate the sum of 3 element in javascript or 3sum?](https://stackoverflow.com/questions/61647764/how-to-calculate-the-sum-of-3-element-in-javascript-or-3sum). Recursion makes no sense on this algorithm because the problem space only reduces linearly per recursive call. If you're trying to learn recursion, it's best to pick problems that make sense for the paradigm, like binary tree traversals, which have a > 1 branching factor. Also, you never actually call `threeSum` recursively in your "recursive" solution attempt. – ggorlen Aug 15 '21 at 21:42

2 Answers2

1

Generators make recursion a bit easier because you can just yield the results. Here the base case is a set of three numbers and a total that equals the values passed in (or no more numbers).

Then just take the first number, add it to found, use it to adjust the total and found numbers and recurse with the rest:

function* threeSum(a, total, found = []) {
  if (found.length == 3) {
    if (total == 0) yield found
    return
  }
  if (a.length == 0) return

  yield* threeSum(a.slice(1), total - a[0], [...found, a[0]])
  yield* threeSum(a.slice(1), total, found)

}

console.log([...threeSum([12, 3, 1, 2, -6, 5, -8, 6], 0)])
Mark
  • 90,562
  • 7
  • 108
  • 148
0

As pointed out, recursion may not be the best approach, but if you must use it, ...

The idea here is at each level of recursion, you make the problem smaller (by using one of the numbers), and then recurse on the 'rest of the array'. You stop after 3 numbers are used or you go over the target.

This is called Backtracking.

    <div id=divvie> </div>

    <script>
    var html = "";
    var target = 23; // or pass it down

    function threesum(subsum, sumsofar, n, Arr, istart)
    {
     var i;
     if (n == 0)
       {
        if (sumsofar == target)
           html += subsum + "<br>";
        return;
       }
     for (i = istart; i < Arr.length; i++)
       {
        var j = Arr[i];
        if (sumsofar + j <= target)
           threesum(subsum + "," + j, (sumsofar+j), n-1, Arr, i+1);
       }
    }

    threesum(target + " = ", 0, 3, [8, 5, 2, 6, 9, 7, 4, 1, 12, 3], 0);

    document.getElementById("divvie").innerHTML = html;
    </script>

Output is:
    23 = ,8,6,9
    23 = ,8,12,3
    23 = ,5,6,12
    23 = ,2,9,12
    23 = ,7,4,12
T G
  • 445
  • 3
  • 7