Split array into arrays of numbers where the sum is equal to a specific target

Question

I need to create a function that take as parameter an array and a target. It should return an array of arrays where the sum of these numbers equals to the target

sumPairs(array, target) {

}

For example:

sumPairs([1, 2, 3, 4, 5], 7) // output : [[2, 5], [3, 4]]

I know I have to use map(), and probably reduce(), set(), or filter() maybe (I read their documentation in MDN but still cant find out). I tried some ways but I can't get it.

If you guys could help me to find out how to dynamically create arrays and push them into a new array..

I read there some solutions (Split array into arrays of matching values) but I hate to just use created functions without knowing what they really do or how they work.

Answer 1

"The exercise says that it sould be arrays of pairs that sum the target value so I think only 2 items"

If you need a pair that matches a sum and you pick any number from the list, you are left with the following equation to solve num + x = sum where we want to find x. E.g. if you picked 7 and the target sum is 10 then you know you are looking for a 3.

Therefore, we can first construct a counting map of the numbers available in our list linear (O(n)) time and then search for matches in linear time as well rather than brute forcing with a quadratic algorithm.

const nums = [1, 2, 3, 4, 5];

console.log(findSumPairs(nums, 7));

function findSumPairs(nums, sum) {
  const countByNum = countGroupByNum(nums);
  
  return nums.reduce((pairs, num) => {
    countByNum[num]--; 
    const target = sum - num;
    
    if (countByNum[target] > 0) {
      countByNum[target]--;
      pairs.push([num, target]);
    } else {
      countByNum[num]++;
    }
    
    return pairs;
  }, []);
}

function countGroupByNum(nums) {
  return nums.reduce((acc, n) => (acc[n] = (acc[n] || 0) + 1, acc), {});
}

Here's another implementation with more standard paradigms (e.g. no reduce):

const nums = [1, 2, 3, 4, 5];

console.log(findSumPairs(nums, 7));

function findSumPairs(nums, sum) {
  const countByNum = countGroupByNum(nums);
  const pairs = [];

  for (const num of nums) {
    const target = sum - num; //Calculate the target to make the sum
    countByNum[num]--; //Make sure we dont pick the same num instance

    if (countByNum[target] > 0) { //If we found the target
       countByNum[target]--;
       pairs.push([num, target]);
    } else {
       countByNum[target]++; //Didin't find a match, return the deducted num
    }
  }

  return pairs;
}

function countGroupByNum(nums) {
  const countByNum = {};

  for (const num of nums) {
    countByNum[num] = (countByNum[num] || 0) + 1;
  }

  return countByNum;
}

Answer 2

You can also sort your array and find all the pairs with given sum by using two pointer method. Place the first pointer to the start of the array and the second pointer to the end.

if the sum of the values at the two places is :

1. More than target: Decrement your second pointer by 1
2. Less than target: Increment your first pointer by 1
3. Equal to target: This is one possible answer, push them to your answer array and increment your first pointer by 1 and decrement your second pointer by 1.

This is more performant solution with complexity O(n*log(n))

Answer 3

Some very basic code for achieving it, Just run all over combinations and conditionally add the items you want.

function sumPairs(array, target) {
  var res = [];
  for(var i = 0; i < array.length; i++){
    for(var j = 0; j < array.length; j++){
      if(i!=j && array[i]+array[j]==target && 
      res.filter((x)=> x[0] == array[j] && x[1] == array[i]).length == 0 )
        res.push([array[i], array[j]]);
    }
  }
  return res;
}

var result = sumPairs([1, 2, 3, 4, 5], 7);
console.log(result);

Option 2 - see this answer for more options (like using reduce)

function sumPairs(array, target) {
  return array.flatMap(
    (v, i) => array.slice(i+1).filter(w => (v!=w && v+w==target)).map(w=> [w,v])
  );
}

var result = sumPairs([1, 2, 3, 4, 5], 7);
console.log(result);