Partition Equal Subset Sum

Description

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

 

Example 1:

Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

 

Example 2:

Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

 

Solution(javascript)

// const canPartition = (nums = []) => {
//   const sum = nums.reduce((acc, number) => number + acc, 0)
//   if (sum % 2 !== 0) {
//     return false
//   }
//   const aux = (list = [], current = 0) => {
//     if (current > sum / 2) {
//       return false
//     }
//     if (current === sum / 2) {
//       return true
//     }
//     return list.some((number, index) => aux(
//       list.filter((_, index2) => index2 !== index),
//       current + number,
//     ))
//   }
//   return aux(nums, 0)
// }


const canPartition = (nums = []) => {
  const sum = nums.reduce((acc, number) => number + acc, 0)
  if (sum % 2 !== 0) {
    return false
  }
  const memo = {}
  const aux = (index, current = 0) => {
    memo[index] = memo[index] || {}
    if (memo[index][current] !== undefined) {
      return memo[index][current]
    }
    if (current > sum / 2) {
      return false
    }
    if (current === sum / 2) {
      return true
    }
    if (index > nums.length) {
      return false
    }
    memo[index][current] = aux(index + 1, current + nums[index]) || aux(index + 1, current)
    return memo[index][current]
  }
  return aux(0, 0)
}