問題描述

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的總和是偶數(shù)；并且總和的一半，稱為maximum，就是partition過后，每一半的總和
• 運(yùn)用動(dòng)態(tài)規(guī)劃，創(chuàng)建一個(gè)數(shù)組dp，記錄從0到maximum間，每個(gè)數(shù)字是否能被其余數(shù)字加出來
  對于nums中的每個(gè)數(shù)字i，從后往前循環(huán)一遍dp中的數(shù)字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):    #必須從后往前，否則會(huì)復(fù)用前面的數(shù)字
                if dp[j - i]:
                    dp[j] = 1
        return dp[maximum] == 1