Leetcode 416 Partition Equal Subset Sum

发表于 |

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200

示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.

分析：

  1. 首先，若sum(nums) % 2 != 0，则显然不可分
  2. 题目演变成在数组中找寻是否有若干个数的和为target，target = sum(nums) / 2
  3. 数组大小不超过200，元素不超过100，则target大小不超过20000

思路：

  1. 建立dp数组，其中dp[i] = 1表示nums中有若干数的和为i，则最后返回dp[target]即可，初始化dp[0] = 1
  2. 依次对nums中的数进行分析，如示例1中[1,5,11,5]，首先对nums[0]进行分析，则可得出dp[1] = 1(因为dp[0] = 1)，然后对nums[1]进行分析，则可得出dp[5] = 1,dp[6] = 1(因为dp[0] = 1,dp[1] = 1)，依次类推
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        s = sum(nums)
        if s & 1: return False
        target = s / 2

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

        for i in xrange(len(nums)):
        	# 必须反向遍历，正向遍历会出现错误
            for j in xrange(target,nums[i]-1,-1):
                if dp[j-nums[i]]: dp[j] = 1

        return [False,True][dp[target]]

104 / 104 test cases passed.
diffculty: medium
Runtime: 926 ms,beats 63.91%