题目描述

[EN | CN]

给定一个 只包含正整数 的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

注意:

  1. 每个数组中的元素不会超过 100
  2. 数组的大小不会超过 200

示例 1:

1
2
3
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

1
2
3
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.

解法 1:0-1 背包

这种分割数组为 2 个子集的问题,其实是 0-1 背包问题 的一个变种,对于数组 nums (记为 $N$)的每一个元素,都可以划分或者不划分到其中一个子集。最终的目标是找到一个 和为所有数字的和(假设是 $s=\sum N$)的一半的子集。接下来我们按照动态规划的步骤分解:

第一步找记忆。对于矩阵 $M$ 中的每一个元素 $M_{i,j}$,其表示了我们只考虑开头的 $i$ 个数字时,能否拼出一个和为 $j$ 的背包(bool 类型)。然后我们最后输出的是元素 $M_{n,\frac{s}{2}}$。

第二步找递推关系式。对于元素 $M_{i,j}$,其递推关系式为: $$ M_{i,j} = \left( \begin{aligned} & N_i == j & \vee \\ & (j > N_i) \wedge (M_{i - 1, j - N_i}) & \vee \\ & M_{i - 1, j} \\ \end{aligned} \right) $$ 其中 $\wedge$ 表示「且」,$\vee$ 表示「或」。我们来解释一下里面每一行:

  1. 第一行表示如果第 $i$ 个数的值 $N_i$ 等于 $j$ 的话,那么只取这个数就能和恰好等于 $j$;
  2. 第二行表示如果目标 $j$ 大于第 $i$ 个数的值 $N_i$ 的话,我们看一下只考虑前 $i-1$ 个数的时候能不能使得找到一个和为 $j - N_i$ 的集合,如果可以的话,这个集合加上当前第 $i$ 的数的值就可以得到一个和为 $j$ 的集合;
  3. 第三行表示如果只考虑前 $i - 1$ 的数就可以拼出和为 $j$ 的组合,那么考虑前 $i$ 个数的时候当然可以。

第三步找初始化。其实比较简单,就是初始化 $M$ 的第 0 行、第 0 列为 False 即可(类似普通 0-1 背包问题 中全部初始化为 0)。

这里还要注意以下如果一开始算所有数字的和为奇数的话,可以直接返回 False。

假设数组长度为 $n$,和为 $c$,那么

  • 时间复杂度为 $O(n \cdot c)$;
  • 空间复杂度为 $O(n \cdot c)$,可优化为 $O(c)$。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_ = sum(nums)
        if sum_ % 2 != 0:
            return False

        n = len(nums)
        c = sum_ // 2
        nums.insert(0, 0)

        m = [[False for _ in range(c + 1)] for _ in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, c + 1):
                if nums[i] == j:
                    m[i][j] = True
                elif nums[i] > j:
                    m[i][j] = m[i - 1][j]
                else:
                    m[i][j] = m[i - 1][j] or m[i - 1][j - nums[i]]

        return m[n][c]
  • 执行用时:2264 ms,在所有 Python3 提交中击败了 21.21% 的用户。
  • 内存消耗:17.8 MB,在所有 Python3 提交中击败了 6.67% 的用户。