LeetCode 416 Partition Equal Subset Sum

LeetCode 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:

1. Each of the array element will not exceed 100.
2. 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.

题目大意：

给定一个只包含正整数的非空数组，判断数组是否可以分成两个和相等的子数组。

解题思路：

这题转化为求是否有子序列的和等于数组和的一半，这就是0-1背包问题。价值和重量是一样数组的背包问题。背包问题递归式：
f[j] = Math.max(f[j], f[j-w[i]]+v[i]);
背包问题最后的解为容量为C的背包能装的最大价值，也就是在这题中，容量为数组一半和的背包能装的最大价值是否为数组一半。如果能，即有解。
表示存在前i个数它的和（最大价值）等于和的一半。
举例说明，容量一半表示刚好可以凑到几个数和为一半，如[1,5,11,5]，容量为11，就可以凑到[1,5,5]重量和价值均为一半。
如[1,2,3,10]和为16，容量为8，只能找到[1,2,3]价值为6达不到一半。所以这里C是限制条件并不是一定要达到。但刚好达到即为解。

注意事项：

1. 数组和为奇数，无解
2. 背包问题的解若为数组一半的和即有解
3. 背包问题解法C向前滚

Java代码：

public boolean canPartition(int[] nums) {
	int sum = 0;
	for(int i=0;i<nums.length;i++)
		sum+=nums[i];
	if(sum%2==1)
		return false;
	int[] result = knapsack(nums,nums,sum/2);
	if(sum/2==result[result.length-1])
		return true;
	return false;
}

public int[] knapsack(int v[], int w[], int C){
	int n = v.length;
	//int[][] re = new int[n][C+1];
	int[] f = new int[C+1];
	
	for(int i=0;i<n;i++){
		for(int j=C;j>=w[i];j--){
			f[j] = Math.max(f[j], f[j-w[i]]+v[i]);
			//if(f[j]==f[j-w[i]]+v[i])
			   // re[i][j] = 1;
		}
	}
	return f;
}

算法分析：

时间复杂度为O(nC)，空间复杂度O(C)。C为数组和的一半，n为数组个数。