class Solution:
  def canPartition(self, num, total_sum):
    
    def solve(index, acc, memo):
      
      if index in memo and acc in memo[index]:
        return memo[index][acc]

      if acc == total_sum:
        return True 

      if index == len(num) and acc != total_sum:
        return False
        
      result = solve(index + 1, acc + num[index], memo) or solve(index + 1, acc, memo)

      if index not in memo:
        memo[index] = {}

      memo[index][acc] = result

      return result

    return solve(0, 0, {})