CODEWITHSUNDEEP
javascriptarraysrecursioncombinations
Manningham
Manningham

Reputation: 332

Using recursion to search all combinations of elements in an array of integers

I am working on this problem from Coderbyte using JS:

Have the function ArrayAdditionI(arr) take the array of numbers stored in arr and return the string true if any combination of numbers in the array can be added up to equal the largest number in the array, otherwise return the string false. For example: if arr contains [4, 6, 23, 10, 1, 3] the output should return true because 4 + 6 + 10 + 3 = 23. The array will not be empty, will not contain all the same elements, and may contain negative numbers.

The problem seems ripe for a recursive solution, given the branching nature of the need to explore the various combinations of array elements. I would also like to use recursion to get some extra practice.. I'm still very new to coding.

Here is the solution I came up with, and I was very happy about it until I started testing and discovered that it is not at all a solution:

function ArrayAdditionI(arr) { 
  // sorting the array to easily remove the biggest value
  var sArr = arr.sort(function (a, b) {
    return a-b;});
  // removing the biggest value
  var biggest = sArr.pop();
  // count will be iterated to stop the recursion after the final element of the array has been processed
  var count = 0;
  function recursion (start, i) {
    if (sArr[i] + start === biggest) {
      return true;
    }
    else if (start + sArr[i] < biggest) {
      return recursion(start + sArr[i], i+1);
    }
    else if (start + sArr[i] > biggest && count < sArr.length) {
      count++;
      return recursion(0, count);
    }
    else {
      return false;
    }
  }
  return recursion(0,0);
}

This code works only if the array elements which can be summed to fulfill the base case are adjacent to each other; calling ArrayAdditionI([1,2,3,4]), for example, will not work because the two elements which must be summed to reach the target value("1" in position 0, and "3" in position 2) are not adjacent.

My flow will return 1, then 1+2, then 1+2+3, then 2, then 2+3, then 3, and finally return false since the target (4) was not reached.

I can visualize how a proper solution needs to flow through a given array, but I don't know how to make this happen through recursion. For the given array [1,2,3,4], the flow should check results in this pattern: (position0, pos0+pos1, pos0+pos2, pos0+pos1+pos2, pos2, pos2+pos3, pos3). Can anyone give me a nudge? I'm going to think on this more before I sleep in an hour and give it a fresh go in the morning.. maybe my brain just needs a recharge.

Again, I'm really new to this, if I've made some very silly mistakes please let me know, I'll learn from them. Thanks!

Upvotes: 2

Views: 2619

Answers (2)

Manningham
Manningham

Reputation: 332

function ArrayAdditionI (arr) {
    var sArr = arr.sort(function (a,b) {
        return a-b;
    });
    var biggest = sArr.pop();
    function recursion (start, indx) {
        if (start + sArr[indx] === biggest) {
            return true;
        }
        else if (sArr.length < indx) {
            return false;
        }
        else if (start + sArr[indx] < biggest) {
            return recursion(start + sArr[indx], indx + 1) || recursion(start, indx+1)
        }
        else {
            return false;
        }
    }
    return recursion(0,0);
}

Upvotes: 1

sectus
sectus

Reputation: 15464

Your algorithm has a flaw. Your function looks only one step forward. You need to add loop inside to look over all rest values.

function ArrayAdditionI(arr) {
    // sorting the array to easily remove the biggest value
    // slice added to prevent original array modification
    var sArr = arr.slice().sort(function (a, b) { 
        return a - b;
    });
    // removing the biggest value
    var biggest = sArr.pop();
    function recursion(start, i) {
        var result = false;
        // looking over all rest values of array
        for (var j = i; j < sArr.length && !result; j++) {
            if (sArr[j] + start === biggest) {
                result = true;
            }
            else if (start + sArr[j] < biggest) {
                result = recursion(start + sArr[j], j + 1);
            }
        }
        return result;
    }
    return recursion(0, 0);
}

Upvotes: 2

Related Questions