算法1
(背包问题)
Time complexity: O(n)
Space complexity: O(n^2)

class Solution:
    def canPartition(self, nums: List[int]) -> bool:

        #Time Complexity: O(n)
        #Space Complexity: O(n)

        Sum = sum(nums)

        if Sum % 2 == 1:
            return False

        Sum = Sum//2

        n = len(nums)

        dp = [0]*(Sum+1)
        dp[0] = 1

        for i in range(1, n+1):
            dp_new = dp.copy()

            for j in range(1, Sum+1):
                if j - nums[i-1] >= 0 and dp[j-nums[i-1]]:
                    dp_new[j] = 1
            dp = dp_new


        return dp[-1]

算法2
（背包问题）
Time complexity: O(n)
Space complexity: O(n)

class Solution:
    def canPartition(self, nums: List[int]) -> bool:

        #Time Complexity: O(n)
        #Space Complexity: O(n) (specifically O(n) for only one array)

        Sum = sum(nums)

        if Sum % 2 == 1:
            return False

        Sum = Sum//2

        n = len(nums)

        dp = [0]*(Sum+1)
        dp[0] = 1

        for i in range(1, n+1):

            for j in range(Sum, 0, -1):
                if j - nums[i-1] >= 0 and dp[j-nums[i-1]]:
                    dp[j] = 1                

        return dp[-1]

算法3
（DFS with Memo）
Time complexity: O(n)
Space complexity: O(n)

class Solution:
    def canPartition(self, nums: List[int]) -> bool:

        #Time Complexity: O(n)
        #Space Complexity: O(n)

        Sum = sum(nums)

        if Sum % 2 == 1:
            return False

        Sum = Sum//2

        n = len(nums)

        dp = [0]*(Sum+1)
        dp[0] = 1

        for i in range(1, n+1):
            dp_new = dp.copy()

            for j in range(1, Sum+1):
                if j - nums[i-1] >= 0 and dp[j-nums[i-1]]:
                    dp_new[j] = 1
            dp = dp_new


        return dp[-1]