p416

发表于 | 分类于 |

LeetCode p416 Partition Equal Subset Sum 题解

1.题目：

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.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

题意：

给一个数组，判断它能不能分成两个和值相等的数组。

2.解题思路:

开始用纯dp超时了了捂脸。。然后围观了大神的动态规划。。居然继续超时了TUT
最后用数组将记录递归。。
先判断这个数组的总和sum 能否被2整除，再考虑下一步。
解析关键语句：dp[j] = dp[j] || dp[j - i];
这句的意思是如果之前我们已经判断出dp[j] 为true 直接为true.
否则考虑dp[j - i]，显然 如果j-i=0,或者某个可以递归为0的数，则为true。
翻译成现实意义就是从这个数组中可以选择几个数相加得到sum/2;
(感觉逻辑解释的有点混乱TUT。。就是这个意思TUT。。看代码更加清晰)

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
public class Solution {
    public boolean canPartition(int[] nums) {
        int len = nums.length;
		if (len == 0)
			return true;
		int sum = 0;
		for (int i : nums) {
			sum += i;
		}
		if (sum % 2 != 0)
			return false;
		sum = sum / 2;
		boolean[] dp = new boolean[sum + 1];
		dp[0] = true;// 其余都初始化为false
		for (int i : nums) {
			for (int j = sum; j >= i; j--) {
				dp[j] = dp[j] || dp[j - i];
			}
		}
		return dp[sum];
    }
}

4.一些总结：好久没有写算法了的感觉。。果然手会生。。工科汪结束了5门结业的期中考～

继续投入代码的怀抱。