string addition I coderbyte completely stumped

Question

Can anyone explain the solution to me like a 6 year old? I haven't been able to make sense of the solutions. Maybe some code comments?

Thank you.

I've spent the last 2 hours on coderbyte trying to solve this one. Here's the question:

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.

I've scoured the internet, read through a bunch of people's solutions from the people's answers on coderbyte itself, but without any comments I'm really struggling to figure out how this is done. I've started over countless times, so I'm not even sure if this last attempt is any better or not.

I understand that I'll need to loop through somehow and test every combination index 5, index 4, index 3, index 2, index 1, AND every combination of less than all of those (ie just index 5 and index 3). I just can't figure out how to do that. If I knew the list would always be an array of 5 numbers, and it required all 5, I would write 5 loops all equally nested inside of one big one, right? However, with the added complexity of not requiring all numbers and not knowing the length of the array for all cases, I am completely stumped. I tried using Math.floor(Math.random() * array.length); to generate a list of numbers... but that didnt work either.

function ArrayAdditionI(arr) { 
  var longest = arr.sort( function(a,b) { return a-b });
  var longest = longest[longest.length - 1];

  var sumArr = function (arrb) {
    var sum = 0;
    for (var z = 0; z < arrb.length; z++){
      sum += arrb[z];
    }
    return sum;
  };

  for (var i = 0; i > arr.length; i++) {
    for (var y = 0; y > arr.length; i++) {
    testArr.push(arr[i]);
    if (sumArr(testArr) === longest) {
      return true;
    }
    testArr.push(... its 4am and I'm stumped!...)
    }}


  // code goes here  
  return false; 

}

// keep this function call here 
// to see how to enter arguments in JavaScript scroll down
ArrayAdditionI(readline());

Take a break, come back later and google for subset sum problem — thefourtheye, Apr 24 '14 at 11:17
Your solution can be found by slightly modifying http://stackoverflow.com/questions/5585104/how-to-implement-the-sum-of-subsets-problem-in-java — Menelaos, Apr 24 '14 at 11:24

score 1 · Answer 1 · answered May 20 '14 at 04:22

A fairly simple to understand and common solution to the problem is as follows. It basically starts by looping forward through the array (loop i) by adding each subsequent number (loop j). If loop j finishes without a solution, loop k begins and removes each subsequent number. Then i increments and the loops start over.

function ArrayAdditionI(arr) { 
  arr.sort(function(a,b){return a - b})
  var largest = arr.pop();  // Set largest to last (largest) array value
  var sum = 0;
  for (var i = 0; i < arr.length; i++){     // Start outer loop 
    sum += arr[i];
    for (var j = 0; j < arr.length; j++){   // Start inner to begin sum
      if (i != j) {     // Ensure we don't add the same array index to itself
        sum += arr[j];
        console.log(sum);
        if (sum == largest) {
          return true;
        }
      }
    }
    for (var k = 0; k < arr.length; k++) {  // If no match, start 2nd loop to re-iterate removing index values
      if (i != k) {
        sum -= arr[k];
        console.log(sum);
        if (sum == largest) {
          return true;
        }
      }
    }
    sum = 0;    // Reset sum for outer loop
  }
  return false; 
}

nice! I just added in a recursion version this morning. odd coincidence I hadn't looked at this problem in weeks. — InfinteScroll, May 20 '14 at 19:17

score 0 · Answer 2 · edited May 23 '17 at 12:17

The comment by thefourtheye basically told you the name of the problem and what to search for on google.

Solutions in java code would be the following...

1) find all subsets that sum to a particular value

This is the theory and pseudocode.

2) How to implement the Sum of Subsets problem in Java

Change the code to return what you wish if number of sets > 0 .

3) Modify GetAllSubsetByStack in below code to stop when a set is found:

https://codereview.stackexchange.com/questions/36214/find-all-subsets-of-an-int-array-whose-sums-equal-a-given-target

score 0 · Answer 3 · answered May 20 '14 at 19:16

We did a similar recursion for a "MakeChange" algorithm at a meetup I went to last night. This morning I took a look at this problem with fresh eyes after not looking at it for a few weeks. Here's what I came up with.

Essentially: sort the array to biggest to smallest, shift that one off and declare it "goal", then recursively reduce an array by slicing it smaller and smaller each recurse, when the array reaches 0 length, randomize the original array and begin reducing again.

return true if goal = total (ie the reduce) return false if ive randomized the array more than 1000 times.

function ArrayAdditionI(arr) {

  var originalArr = arr.sort(function(a,b) {return b-a});
  var goal = arr.shift();
  var counter = 0;

  function randomArray(array) {
    for (var i = array.length - 1; i > 0; i -= 1){
      var j = Math.floor(Math.random() * (i + 1));
      var temp = array[i];
      array[i] = array[j];
      array[j] = temp;
    }
    return array;
  }

  function recurse(arr) {
    if (arr.length == 0){
      counter++
      var newArr = randomArray(originalArr);
      return recurse(newArr);

    } else {

      var total = arr.reduce(function(a,b) {return a+b});

      if (goal == total){
        return true

      } else if (counter == 1000) {
        return false 

       } else {
         newArr = arr.slice(1);
         return recurse(newArr);


       }
    } 
  }

  // code goes here  
  return recurse(originalArr); 

}

string addition I coderbyte completely stumped

3 Answers3