What is the primary dynamic programming pattern used to solve the Partition Equal Subset Sum problem?

The primary pattern used is state transition dynamic programming, where we track which subset sums are achievable using an array of possible sums.

How do we handle optimization in the Partition Equal Subset Sum problem?

Optimization is achieved by using a 1D DP array instead of a 2D one and updating it in reverse order to prevent overwriting results in the same iteration.

Can the Partition Equal Subset Sum problem be solved with a greedy approach?

No, the problem cannot be solved with a greedy approach since the partitioning is not guaranteed to follow a simple greedy selection of elements.

What happens if the total sum of the array is odd?

If the total sum is odd, it is immediately impossible to partition the array into two subsets with equal sum, and the answer should be false.

What is the time complexity of the solution?

The time complexity is O(n * sum), where `n` is the number of elements and `sum` is half of the total sum of the array.

#416

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

分割等和子集

给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。示例 1：输入： nums = [1,5,11,5] 输出： true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。示例 2：输入： nums = [1,2…

数组动态规划

题目描述

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

示例 1：

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

示例 2：

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

提示：

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

lightbulb

解题思路

方法一：动态规划

我们先计算出数组的总和 $s$ ，如果总和是奇数，那么一定不能分割成两个和相等的子集，直接返回 $false$ 。如果总和是偶数，我们记目标子集的和为 $m = \frac{s}{2}$ ，那么问题就转化成了：是否存在一个子集，使得其元素的和为 $m$ 。

我们定义 $f[i][j]$ 表示前 $i$ 个数中选取若干个数，使得其元素的和恰好为 $j$ 。初始时 $f[0][0] = true$ ，其余 $f[i][j] = false$ 。答案为 $f[n][m]$ 。

考虑 $f[i][j]$ ，如果我们选取了第 $i$ 个数 $x$ ，那么 $f[i][j] = f[i - 1][j - x]$ ；如果我们没有选取第 $i$ 个数 $x$ ，那么 $f[i][j] = f[i - 1][j]$ 。因此状态转移方程为：

f[i][j] = f[i - 1][j] \textit{ or } f[i - 1][j - x] \textit{ if } j \geq x

最终答案为 $f[n][m]$ 。

时间复杂度 $(m \times n)$ ，空间复杂度 $(m \times n)$ 。其中 $m$ 和 $n$ 分别为数组的总和的一半和数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        m, mod = divmod(sum(nums), 2)
        if mod:
            return False
        n = len(nums)
        f = [[False] * (m + 1) for _ in range(n + 1)]
        f[0][0] = True
        for i, x in enumerate(nums, 1):
            for j in range(m + 1):
                f[i][j] = f[i - 1][j] or (j >= x and f[i - 1][j - x])
        return f[n][m]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Understanding of dynamic programming
question_mark
Ability to optimize space complexity
question_mark
Awareness of state transitions in dynamic programming solutions

warning

常见陷阱

外企场景

error
Assuming the array can always be partitioned without checking if the sum is even
error
Incorrectly updating the DP array leading to false positives
error
Not handling edge cases like very small or large numbers in the array correctly

swap_horiz

进阶变体

外企场景

arrow_right_alt
If the array contains negative numbers
arrow_right_alt
If the array is sorted or unordered
arrow_right_alt
If there are multiple ways to partition the array

help

常见问题

外企场景

继续练习

#413 等差数列划分 #410 分割数组的最大值 #403 青蛙过河