subarray_sum_fb.js

// ==Question==

// Given a sequence of integers and an integer total target, return whether a contiguous sequence of integers sums up to target.

// ===Example===

// [1, 3, 1, 4, 23], 8 : True (because 3 + 1 + 4 = 8)
// [1, 3, 1, 4, 23], 7 : False

// total = 9
// [1, 3, 1, 4, 23], 8
// .^           
//           ^


// [1, 3, 1, 4, 23], 8

// solution([1, 3, 1, 4, 23], 8, n = 5, left = 0, right = 0, total = 0)
// solution([1, 3, 1, 4, 23], 8, n = 5, left = 0, right = 1, total = 1)
// solution([1, 3, 1, 4, 23], 8, n = 5, left = 0, right = 2, total = 4)
// solution([1, 3, 1, 4, 23], 8, n = 5, left = 0, right = 3, total = 5)
// solution([1, 3, 1, 4, 23], 8, n = 5, left = 0, right = 4, total = 9) // returns true

// total = 4
// [3, -1, 1, 1, 4, 23], 48
//         ^
// ^

// total = 4
// target = 5
// [3, -1, 1, 1, 4, 23], 48

const solution = (arr, target, n = arr.length, left = 0, right = 0, total = 0) => {
  if (!arr || arr.length === 0) return false;
  
  if (target === 0) return true;
  
  if (right > n || left > n) return false;
  
  if (total === target) return true;
  
  if (total < target) return solution(arr, target, n, left, right + 1, total + arr[right]);
  
  return solution(arr, target, n, left + 1, right, total - arr[left]);
};


const solution2 = (arr, target) => {
  const cumSumMap = new Map();
  let sum = 0;
  return arr.some(val => {
    sum += val;
    cumSumMap.set(sum, true);
    return (val === target || cumSumMap.has(target - val));
  });
}