leetcode 416. Partition equal subset sum partition equal subset sum (medium)

One 、 The main idea of the topic

label :  Dynamic programming

https://leetcode.cn/problems/partition-equal-subset-sum

To give you one   Contains only positive integers   Of   Non empty   Array  nums . Please decide whether you can divide this array into two subsets , Make the sum of the elements of the two subsets equal .

Example  1：

Input ：nums = [1,5,11,5] Output ：true explain ： Arrays can be divided into  [1, 5, 5]  and  [11] .

Example  2：

Input ：nums = [1,2,3,5] Output ：false explain ： An array cannot be divided into two elements and equal subsets .

Tips ：

1 <= nums.length <= 2001 <= nums[i] <= 100

Two 、 Their thinking

Set the sum of all numbers to sum, Our goal is to select a sub array , Make its sum equal to sum/2, Define two dimensions boolean Array dp[i][j], Its meaning is before use i Can the sum of numbers form an integer j. We need to traverse every position , At the same time 0-target All positive numbers between . The state transition equation is , Traversing i Can the position constitute target= The sum of the preceding numbers can form target|| The preceding numbers can form target-nums[i]. The two statuses are "select" or "not" nums[i] In two cases , If one of the cases is true ：dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]

3、 ... and 、 How to solve the problem

3.1 Java Realization

public class Solution {
 public boolean canPartition(int[] nums) {
 //  Array sum
 int sum = Arrays.stream(nums).sum();
 //  scene 1： And are odd and cannot be divided equally
 if (sum % 2 == 1) {
 return false;
 }
 int target = sum / 2;
 int n = nums.length;
 boolean[][] dp = new boolean[n + 1][target + 1];
 dp[0][0] = true;
 for (int i = 1; i <= n; i++) {
 for (int j = 0; j <= target; j++) {
 if (j < nums[i - 1]) {
 dp[i][j] = dp[i - 1][j];
 } else {
 dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
 }
 }
 }

 return dp[n][target];
 }
}


Four 、 Summary notes

• 2022/6/29  expect 7.5 Number