text: # Time:  O(n * s), s is the sum of nums
  # Space: O(s)
  
  class Solution(object):
      def canPartition(self, nums):
          """
          :type nums: List[int]
          :rtype: bool
          """
          s = sum(nums)
          if s % 2:
              return False
  
          dp = [False] * (s/2 + 1)
          dp[0] = True
          for num in nums:
              for i in reversed(range(1, len(dp))):
                  if num <= i:
                      dp[i] = dp[i] or dp[i - num]
          return dp[-1]
  
  