Given a nonempty array nums, which only contains positive number. Find if the array can be divided into two parts such that the sum of each part is equal.
Input: nums = [1,5,11,5]
Output: true
Explanation: divide into [1,5,5] and [11].
To satisfy two part sum are equal, then each part sum is half of total sum. If the total sum is an odd or the max number in the array is bigger than half of total sum, then it’s can’t satisfy the requirement.
This problem is similar to 0-1 package problem. What differs is that the total sum we chose can’t exceed the capacity of the package in 0-1 package problem, while the chosen number’s sum must equal to half of total sum in this question. Similar to traditional 0-1 package problem, we can use dynamic programming to solve this problem.
We use a two-dimensional array boolean dp[n][half+1] for dynamic programming. Where n is the length of nums and half is the half of total sum. We define dp[i][j]:
-
iranges from 0 ton-1, which means the subset(0, i) ofnums. -
jranges from 0 tohalf, which means if the subset(0, i) can constitute a sum of valuej.
dp[i][j] is true if subset(0, i) of nums can constitute a sum of value j. Then dp[n-1][half] means in the whole array nums, if it can constitute a sum of half.
The state transition equation is as follows:
[dp[i][j]=\begin{cases} dp[i-1][j]\ ||\ dp[i-1][j-num[i]]&num[i]\leq j\ dp[i-1][j]&num[i]>j \end{cases}]
dp[i][j] means we are deciding if we count nums[i] to constitute a sum of j for subset(0, i).
The upper case means: nums[i]<=j< code>, if we not choose this number, then our result(can constitute or not) is equal to "if the subset(0, i-1) can constitute a sum of <code>j</code>", that is<code>dp[i-1][j]</code>. If we choose this number, then our result is equal to "if the subset(0, i-1) can constitute a sum of <code>j-num[i]</code>". Either of them is true, then we can constitute a sum of <code>j</code> by subset(0, i) of <code>nums</code>.<br>The lower case means: <code>nums[i]>j</code>, the number is bigger than the number(<code>j</code>) we want to constitute, so we can't choose. Our result is same as <code>dp[i-1][j]</code>.<!--=j<-->
Observe the transition equation, we found that each line of our two-dimensional array dp only related to the previous line(dp[i] is decided by dp[i-1] only). So we can store the dp in only one line:
When we handle the new line i, the 1-dimensional array stores the i-1 line data! For each line, we ranges j from half to 0. The new state transition equation is as follows:
[dp[j]=dp[j]\ ||\ dp[j-nums[i]] ]
Since j ranges from half to 0, dp[j] or dp[j-nums[i] store the date of last line(i-1). After each round of j, we updated a line.
If nums.length<2< code> or <code>sum(nums)</code> is odd or <code>max(nums)>sum(nums)/2</code>, return <code>false</code>.<br>Create a boolean array <code>dp[sum(nums)/2+1]</code>. For <code>i</code> in range from 0 to <code>num.length</code>, for <code>j</code> in range from <code>sum(nums)/2</code> to 0, if <code>dp[j]==true</code> or <code>dp[j-nums[i]==true</code>, the <code>dp[j]=true</code>.<br>Finally, return <code>dp[sum(nums)/2]</code>.<!--2<-->
The detailed code is as follows
public class p416 {
public static boolean canPartition(int[] nums) {
int len = nums.length;
if (len < 2) {
return false;
}
int totalSum = 0, half = 0, maxNum = 0;
for (int num : nums) {
totalSum += num;
maxNum = Math.max(maxNum, num);
}
if (totalSum % 2 != 0 || totalSum / 2 < maxNum) {
return false;
}
half = totalSum / 2;
boolean[] dp = new boolean[half + 1];
dp[0] = true;
for (int i = 0; i < len; i++) {
int num = nums[i];
for (int j = half; j >= num; j--) {
dp[j] = dp[j] | dp[j - num];
}
}
return dp[half];
}
}
Time complexity: The outer loop nums.length, the inner loop sum(nums)/2, so the total time complexity is O(nums.length × sum(nums)/2)
Space complexity: After optimization, the space we used are sum(nums)/2, so the total space complexity is O(sum(nums)/2)
Original: https://www.cnblogs.com/liuzhch1/p/16197049.html
Author: liuzhch1
Title: LeetCode 416.分割等和子集 | 类0-1背包问题 | 解题思路及代码
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/620672/
转载文章受原作者版权保护。转载请注明原作者出处！