416. Partition Equal Subset Sum

问题描述

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:
Each of the array element will not exceed 100.
The array size will not exceed 200.

思路

• 能被partition说明nums的总和是偶数；并且总和的一半，称为maximum，就是partition过后，每一半的总和
• 运用动态规划，创建一个数组dp，记录从0到maximum间，每个数字是否能被其余数字加出来
  对于nums中的每个数字i，从后往前循环一遍dp中的数字j，范围是maximum到i
  如果j-i存在，则说明j值可以被凑出来，在dp中记录1
  最后返回dp[maximum]==1

    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if sum(nums) %2 != 0:
            return False
        maximum = sum(nums)//2
        dp = [0]*maximum
        dp.insert(0,1)
        for i in nums:
            for j in range(maximum, i - 1, -1):    #必须从后往前，否则会复用前面的数字
                if dp[j - i]:
                    dp[j] = 1
        return dp[maximum] == 1