Dynamic nested loops over array

Question

I'm trying to figure out how to dynamically doing a deep looping over an array.
Lets say i have a function that takes an array of numbers and a total number, it will loop over the array and will return a tuple of the numbers that together make the sum of the total:

const sumOfTwo = (arr, total) => {
  let map = {};

  for (let currentNum of arr) {
    if (map[currentNum] !== undefined) {
      return [map[currentNum], currentNum]
    } else {
      map[total - currentNum] = currentNum;
    }
  }
  return [];
}

const num = 6
const arr = [4, 5, 2, 3, 1];
const result = sumOfTwo(arr, num);
console.log(result); // [4, 2]

Now if i want to create the same function but that finds a sum of three numbers, i will have to do a nested loop:

function sumOfThree(arr, total) {
  for (let i = 0; i < arr.length; i++) {
    let processed = {};
    let firstNum = arr[i];
    let firstDelta = total - firstNum;
    for (let j = i + 1; j < arr.length; j++) {
      let secondNum = arr[j];
      let secondDelta = firstDelta - secondNum;
      if (processed[secondDelta]) {
        return [firstNum, secondNum, secondDelta];
      }
      processed[secondNum] = true;
    }
  }
  return [];
}

const arr = [1, 2, 3, 4];
const sum = 6;
const result = sumOfThree(arr, sum);
console.log(result); // [1, 3, 2]

If i want a sumOfFour function, i guess i need another nested loop and so on.

What i actually want is to create a generic function sumOf that will take the array, the total but also that number of numbers it should add up to the total. I was thinking of doing a recursive flow but got stuck on the very first line, now i'm not so sure it can be done.

Any suggestion would be much appropriated

The simplest solution to this is to use lodash ._sum lodash.com/docs/4.17.11#sum — Michael
– Michael, Commented Mar 13, 2019 at 20:18

Jonas Wilms · Accepted Answer · 2019-03-13 20:42:32Z

2

Generators are really useful then to yield values up, also you can pass down the previous sum and values through the recursion:

function* sumUp(values, target, n, previous = [], sum = 0) {
  // Base case: if the combination of n values is target, yield it, or exit
  if(n <= 0) {
    if(sum === target) yield previous;
    return;
  }

  // otherwise add this combo
  for(const value of values) {
    // don't use the same number twice
    if(previous.includes(value)) continue;

    yield* sumUp(values, target, n - 1, [...previous, value], sum + value);       
  }
}

Usable as:

  // all combinations
 console.log([...sumUp([1, 2, 3, 4], 7, 2)]);
 // just the first
 console.log(sumUp([1, 2, 3, 4], 7, 2).next().value);

edited Mar 13, 2019 at 20:42

answered Mar 13, 2019 at 20:20

Jonas Wilms

139k20 gold badges164 silver badges164 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

jasDotnet Over a year ago

Thank you! 2 problems though, 1) not sure i can use generators in my project, so i was looking for a regular function solution. 2) the numbers cannot get repeated, i mean if n is 4 it will yield [1, 1, 1, 4]. in this case i would like to get an empty array, same as my example above.

Jonas Wilms Over a year ago

@jasDotnet 2) edited, 1) replace yield with return and yield* with const v = /*...*/; if(v) return v;

jasDotnet Over a year ago

Great, thanks a lot! will examine the code to understand it better

Collectives™ on Stack Overflow

Dynamic nested loops over array

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related