当前位置：首页 > news >正文

动态规划题解——分割等和子集【LeetCode】

news 2025/7/18 21:47:11

416. 分割等和子集

一、算法逻辑（每一步思路）

❓ 问题描述：

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

✅ 思路解析（DFS + 记忆化）

1. 总和判断：

s = sum(nums)

只有当总和是偶数时，才可能被分成两个相等的子集；
否则直接返回 False。

2. 定义目标：

我们目标是找到一个子集，使得其和为 target = s // 2。

3. 定义状态：

dfs(i, j) 表示：是否可以从 nums[0..i] 中选出一些数，使得它们的和为 j

4. 状态转移逻辑：

我们每个数都可以选或不选：

dfs(i, j) = dfs(i-1, j-nums[i])  # 选 nums[i]or dfs(i-1, j)          # 不选 nums[i]

前提是：

当选 nums[i] 时，必须保证 j >= nums[i] 否则非法。

5. 边界条件：

i < 0 表示没有数可以选了，此时只有当 j == 0，才能说“成功凑出目标和”。

6. 初始调用：

dfs(len(nums)-1, s//2)

从所有数中尝试凑出 s//2。

7. 使用 `@cache` 实现记忆化，避免指数级重复递归。

二、算法核心点

✅ 核心思想：子集和问题 + 记忆化搜索

本质是 0/1 背包问题：能不能从 nums 中挑若干个数，使它们的和为 target = s // 2
DFS 方式天然适合尝试所有选法；
用记忆化优化重复状态访问，转为多项式级别复杂度。

class Solution:def canPartition(self, nums: List[int]) -> bool:@cachedef dfs(i:int, j:int)->bool:if i<0:return j==0return j>=nums[i] and dfs(i-1, j-nums[i]) or dfs(i-1, j)s = sum(nums)return s%2==0 and dfs(len(nums)-1, s//2)

三、复杂度分析

时间复杂度：O(n × target)

- 每个状态 (i, j) 最多访问一次；
- i 最多为 n，j 最多为 target = s//2

空间复杂度：O(n × target)

- 缓存表大小为 n × target；
- 递归栈深度最多为 n

总结表

维度	内容
✅ 思路逻辑	转化为是否可以从数组中选出若干数，使它们的和为总和的一半
✅ 核心技巧	记忆化搜索 + 状态定义 `dfs(i, j)`
✅ 时间复杂度	O(n × s//2)，即 O(n × sum/2)
✅ 空间复杂度	O(n × sum/2)，包括递归栈和缓存