/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
/*
 Recursion Unoptimized Approach:
 Can recursively try to add the current number or subtract the current number and check if at the end it reaches the target sum
 Since we're making 2 choices every time in the recursive step, this involves O(2^n) time plus the call stack space usage
*/
var findTargetSumWays = function(nums, target) {
 function recFindTargetSumWays(currentIndex, currentSum) {
   // Base Cases
   // Once we hit the end of the array, we check if the currentSum matches with the target 
   // If it does, we bump the numResultsReachingTarget
   if (currentIndex >= nums.length && currentSum === target) {
     numResultsReachingTarget += 1;
     return;
   // Otherwise, we return and don't bump anything
   } else if (currentIndex >= nums.length && currentSum !== target) {
     return;
   }
   
   // Recursive Step
   // Figure out if we can reach the target sum by recursively adding the currentNum or subtracting the currentNum 
   const currentNum = nums[currentIndex];
   recFindTargetSumWays(currentIndex+1, currentSum + currentNum);
   recFindTargetSumWays(currentIndex+1, currentSum - currentNum);
 }
 
 let numResultsReachingTarget = 0;
 recFindTargetSumWays(0, 0);
 return numResultsReachingTarget
};