代码随想录——分割等和子集（Leetcode LCR 101）
题目链接
0-1背包问题
class Solution {public boolean canPartition(int[] nums) {int[] dp = new int[10000];int sum = 0;// 首先求背包体积应该为nums数组总和的一半for(int i = 0; i < nums.length; i++){sum += nums[i];}// 如果总和为奇数则不存在等和子集if(sum % 2 == 1){return false;}int target = sum / 2;// 0-1背包，注意一维dp数组先背包后体积，体积倒序遍历保证每个物品只出现一次for(int i = 0; i < nums.length; i++){for(int j = target; j >= nums[i]; j--){// 递推公式dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}}// 集合元素正好凑成总和targetif(dp[target] == target){return true;}else{return false;}}
}
本题思想：题目中物品是nums[i]，重量是nums[i]，价值也是nums[i]，背包体积是target = sum / 2
如果使用暴力求解，应使用回溯算法。