剑指 Offer II 101. 分割等和子集

Posted on | In
Words count in article: 240 | Reading time ≈ 1

题目

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

示例1：

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

示例2：

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

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

解法一：

JAVA

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
public boolean canPartition(int[] nums) {
        // 数组和的一半，也是最终背包的容量
        int mid = 0;
        for (int num : nums) {
            mid += num;
        }
        if (mid % 2 != 0) {
            return false;
        }
        mid >>= 1;

        boolean[][] f = new boolean[nums.length + 1][mid + 1];
        f[0][0] = true;
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j <= mid; j++) {
                // 不选中第i个的情况
                f[i][j] = f[i - 1][j];
                // 选中第i个的情况
                if (!f[i][j] && j >= nums[i - 1]) {
                    f[i][j] = f[i - 1][j - nums[i - 1]];
                }
            }
        }
        return f[nums.length][mid];
    }
0%