【Hot100】LeetCode—416. 分割等和子集

---

• 原题链接：416. 分割等和子集

---

1- 思路

题目识别

• 识别1 ：等和子集

动规五部曲

思路：

• 首先求 sum，如果 sum 是一个奇数 则 不能进行分割 。
• 之后根据 0 1 背包的递推公式 dp[j] = Math.max(dp[j] , dp[j-weights[i]] + values[i]);

---

2- 实现

⭐416. 分割等和子集——题解思路

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for(int i:nums){sum+=i;}if(sum%2!=0) return false;int half = sum/2;// 转换为是否可以填满背包 为 half 的背包问题，商品为 nums//1. 定义 dp 数组int[] dp = new int[half+1];//2. 递推公式// 商品的重量小于 half ，填充// if(nums[i] < half) // 3. 初始化，全为 0// 0-1 背包的遍历顺序// 先物品for(int i = 0 ; i < nums.length ; i++){// 后背包for(int j = half ; j>=nums[i] ; j--){dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);}}return dp[half] == half;}
}

---

3- ACM 实现

public class canPartition {public static boolean canPartition(int[] nums) {int sum = 0;for(int i:nums){sum+=i;}if(sum%2!=0) return false;int half = sum/2;// 转换为是否可以填满背包 为 half 的背包问题，商品为 nums//1. 定义 dp 数组int[] dp = new int[half+1];//2. 递推公式// 商品的重量小于 half ，填充// if(nums[i] < half)// 3. 初始化，全为 0// 0-1 背包的遍历顺序// 先物品for(int i = 0 ; i < nums.length ; i++){// 后背包for(int j = half ; j>=nums[i] ; j--){dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);}}return dp[half] == half;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();input = input.replace("[","").replace("]","");String[] parts = input.split(",");int[] nums = new int[parts.length];for(int i = 0 ; i < nums.length;i++){nums[i] = Integer.parseInt(parts[i]);}System.out.println("结果是"+canPartition(nums));}
}