【leetcode】分割等和子集

一、题目描述

给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。

输入：nums = [1,5,11,5]
输出：true
解释：nums 可以分割成 [1, 5, 5] 和 [11]

输入：nums = [1,2,3,5]
输出：false
解释：nums 不可以分为和相等的两部分

二、代码思路

这是一道经典的NP问题，NP问题太深奥，我们直接讲NP问题中的背包问题反而更容易理解。背包问题，就是一种组合优化的 NP (NP-Complete) 完全问题。

问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

当然这道题也可以当作背包问题来做，而且可以作为背包问题的解题模板，这道题也算是开了背包问题的先河。

我们可以将题目转换为这种思路，从数组中选出几个数使得这几个数之和是数组所有数之和的一半。也就是选出几个数能把背包正好填充。这就转换成背包问题了。

更加详细的解释请看下面连接：

详细讲解了背包问题与该问题的思路：

官方题解，开头讲的好，后面DP讲的一般

三、代码题解

package leetcode.lc20221109;

import java.util.Arrays;
import java.util.stream.Stream;

/*
 * @author lzy
 * @version 1.0
 * */
public class Solution03 {
    public boolean canPartition(int[] nums) {
        //这道题值得记录，算是回溯问题的一种，归类
        //子集问题，我的思路如下：1、dfs回溯找到所有不重复子集。2、在子集中找元素相等的两个子集。
        //复习一下回溯：子集问题用二叉搜索树即可，全排列问题用多叉搜索树（但是不能选自身）
        //动态规划题解（动态规划部分讲不好）：https://leetcode.cn/problems/NUPfPr/solutions/1417796/fen-ge-deng-he-zi-ji-by-leetcode-solutio-re1t/

        //0-1背包问题（讲的不错）：https://leetcode.cn/problems/NUPfPr/solutions/1501730/by-flix-c3fv/
        int total = Arrays.stream(nums).reduce(0,(a,b) -> {
            return  a + b;
        });
        //把一个类中的静态方法作为Lambda体，可以这样用::
        int total1 = Arrays.stream(nums).reduce(0, Integer::sum);
        if (total % 2 == 1) {
            return false;
        }
        int target = total / 2;
        //流取最大值
        int maxNum = Arrays.stream(nums).reduce(nums[0],(a,b) -> {
            return Math.max(a , b);
        });
        if (maxNum > target) {
            return false;
        }
        //为了便于对边界值的判断，所以定义的二维数组，长宽都+1了
        boolean dp[][] = new boolean[nums.length + 1][target + 1];
        //dp[0][0]表示从前0个元素中选出和为0的元素
        dp[0][0] = true;
        for (int j = 1; j < target + 1; j++) {
            dp[0][j] = false;
        }
        for (int i = 1; i < nums.length + 1; i++) {
            for (int j = 0; j < target + 1; j++) {
                //i = 1 代表 nums[0]
                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[nums.length][target];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

使用滚动数组进行空间优化：

class Solution {
    public boolean canPartition(int[] nums) {
        //这道题值得记录，算是回溯问题的一种，归类
        //子集问题，我的思路如下：1、dfs回溯找到所有不重复子集。2、在子集中找元素相等的两个子集。
        //复习一下回溯：子集问题用二叉搜索树即可，全排列问题用多叉搜索树（但是不能选自身）
        //动态规划题解（动态规划部分讲不好）：https://leetcode.cn/problems/NUPfPr/solutions/1417796/fen-ge-deng-he-zi-ji-by-leetcode-solutio-re1t/

        //0-1背包问题（讲的不错）：https://leetcode.cn/problems/NUPfPr/solutions/1501730/by-flix-c3fv/
        int total = Arrays.stream(nums).reduce(0,(a,b) -> {
            return  a + b;
        });
        //把一个类中的静态方法作为Lambda体，可以这样用::
        int total1 = Arrays.stream(nums).reduce(0, Integer::sum);
        if (total % 2 == 1) {
            return false;
        }
        int target = total / 2;
        //流取最大值
        int maxNum = Arrays.stream(nums).reduce(nums[0],(a,b) -> {
            return Math.max(a , b);
        });
        System.out.println(total + " " + maxNum);
        if (maxNum > target) {
            return false;
        }
        //为了便于对边界值的判断，所以定义的二维数组，长宽都+1了
        boolean dp[] = new boolean[target + 1];
        dp[0] = true;
        for (int i = 1; i < nums.length + 1; i++) {
            boolean dp2[] = new boolean[target + 1];
            for (int j = 0; j < target + 1; j++) {
                //i = 1 代表 nums[0]
                if (j < nums[i - 1]) {
                    dp2[j] = dp[j];
                } else {
                    dp2[j] = dp[j] | dp[j - nums[i - 1]];
                }
            }
            dp = dp2;
        }
        return dp[target];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43