/**
* @param {number[]} nums
* @return {boolean}
*/
// Recursion Approach
// Only possible to find two equal subsets if sum(nums) is even
// If it's odd we return false right away
// Need to find a subset that adds up to target where it is sum(nums) / 2
// Can use a recursive helper with currentIndex passed through and currentTarget
// Base Cases
// if currentIndex is outside of bounds i.e. >= nums.length or currentTarget < 0 (overshot it), return false
// if currentIndex is within bounds and currentTarget is 0, return true
// Recursive Step
// Can make 2 choices at each currentIndex element: either we can add the current element to the subset or skip it
// We can check recursively if we can partition by adding the current element 
// i.e. rec(currentIndex + 1, currentTarget - nums[currentIndex]) or 
// skipping the current element i.e. rec(currentIndex + 1, currentTarget)
// O(2^n) time and O(n) function stack space
var canPartition = function(nums) {
 const totalSum = nums.reduce((previousValue, currentValue) => previousValue + currentValue, 0);
 
 // Not possible to find 2 equal subsets if total sum is odd, so we return false
 if (totalSum % 2 === 1) {
   return false;
 }
 
 // It's possible to find 2 equal subsets if total sum is even, so we divide it by 2 and that is our target to find a subset that adds up to this
 const target = totalSum / 2;
 
 const rec = (currentIndex, currentTarget) => {
   // If currentIndex is out of bounds or we overshot the target, we can't partition
   if (currentIndex >= nums.length || currentTarget < 0) {
     return false;
   }
   // If currentTarget is within bounds and currentTarget is 0, we have 2 equal subsets to partition
   if (currentTarget === 0) {
     return true;
   }
   
   // Recursively check if we can add the current element to the subset or skip it
   const canPartitionWithNum = rec(currentIndex + 1, currentTarget - nums[currentIndex]);
   const canPartitionWithoutNum = rec(currentIndex + 1, currentTarget);
   
   return canPartitionWithNum || canPartitionWithoutNum;
 };
 
 return rec(0, target);
};