For a given array, we try to find set of pair which sums up as the given target number.

For example, we are given the array and target as:

const data = [2, 4, 6, 10];const target = 16;

We should be able to find 2 pair, which sum up to 16:

{
   2,4,10}{
    6,10}

We need to create a function to return the number of pair we found, in this case, the answer is: 2

 

const data = [2, 4, 6, 10];/** * Return number of pair found */function DP(data, target = 16) {  let memo = {};  return rc(data, target, data.length - 1, memo);  function rc(data, target, i, memo) {    // Construct the key - value for memo    let key = `${target}-${i}`;    // Store the result    let res = 0;    // return the value if already calcualte    if (memo[key]) {      return memo[key];    }    // if the target is zero, then it is empty set, return 1    if (target === 0) {      return 1;    } else if (target < 0) {      // if target < 0, we don't consider the case, return 0      return 0;    } else if (i < 0) {      // if i <0, means we run out of element, return 0      return 0;    }    // if current value is larger than targer, we continue with next value    if (data[i] > target) {      res = rc(data, target, i - 1, memo);    } else {      /**       * Two cases:       * 1. The current value is not include:       *  rc(data, target, i - 1, memo)       * 2. The current value is include: the rest of els should sum up to new target value       *  rc(data, target - data[i], i - 1, memo)       */      // i is not included + i is included      res =        rc(data, target, i - 1, memo) + rc(data, target - data[i], i - 1, memo);    }    memo[key] = res;    return res;  }}console.log(DP(data, 16)); // 2

 

Time complexity: O(target * n * 2 + 1) = O(T*N)