代码随想录——分割等和子集（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]);
            }
        }
        // 集合元素正好凑成总和target
        if(dp[target] == target){
            return true;
        }else{
            return false;
        }
    }
}

本题思想：题目中物品是nums[i]，重量是nums[i]，价值也是nums[i]，背包体积是target = sum / 2

如果使用暴力求解，应使用回溯算法。