416. 分割等和子集

题目：

416. 分割等和子集

题解：动态规划

代码：动态规划

public class code416 {

    public static boolean canPartition(int[] nums) {
        int len = nums.length;
        if(len == 0)
        {
            return false;
        }
        int sum = 0;
        for(int i = 0; i < len; i++)
        {
            sum += nums[i];
        }
        // 特判：如果是奇数，就不符合要求
        if((sum & 1) == 1)
        {
            return false;
        }

        int target = sum / 2;

        // 创建二维状态数组，行：物品索引，列：容量（包括 0）
        // dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于 j。
        boolean dp[][] = new boolean[len][target + 1];

        // 先填表格第 0 行，第 1 个数只能让容积为它自己的背包恰好装满
        if(nums[0] <= target)
        {
            dp[0][nums[0]] = true;
        }
        // 再填表格后面几行
        for(int i = 1; i < len; i++)
        {
            for(int j = 0; j <= target; j++)
            {
                // 直接从上一行先把结果抄下来，然后再修正
                dp[i][j] = dp[i - 1][j];

                if(nums[i] == j)
                {
                    dp[i][j] = true;
                    continue;
                }
                if(nums[i] < j)
                {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[len - 1][target];
    }
    
    public static void main(String[] args) {
        int nums1[] = { 1, 5, 11, 5 };
        boolean res1 = canPartition(nums1);
        System.out.println(res1);

        int nums2[] = { 1, 2, 3, 5 };
        boolean res2 = canPartition(nums2);
        System.out.println(res2);
    }
}

参考：

1. 动态规划（转换为 0-1 背包问题）
2. 0-1 背包问题变体之子集分割
3. 剪枝就可以，容易理解还高效 – 极其适合初学者理解
4. 416. 分割等和子集
5. JAVA DFS+剪枝 1ms 99.31%
6. JAVA动态规划，执行用时92%、内存消耗89%