class Solution:
  def canPartition(self, num):
    
    def solve(left, right, index, memo):
      # return from memo
      if index in memo and (str(left) + str(right)) in memo[index]:
        return memo[index][(str(left) + str(right))]
      
      # we reached the end
      if index == len(num):
        return False
      
      # we find equality
      if left == right:
        return True

      left_without = left - num[index]
      right_with = right + num[index]

      result = solve(left, right, index + 1, memo) or solve(left_without, right_with, index + 1, memo)
      
      if index not in memo:
        memo[index] = {}

      memo[index][(str(left) + str(right))] = result
      return result

    return solve(sum(num), 0, 0, {})