LC416
分割等和子集
背包 DP · 0/1可视化:动态规划表nums=[1,5,11,5] 能否平分 sum=22→子集和 11。
时间 O(n)空间 O(1)
题目1 / 15
题目与输入建立输入、目标与算法心智
完全背包:每种硬币无限
正在加载算法场景...
当前发生了什么
nums=[1,5,11,5] 能否平分 sum=22→子集和 11。
机器状态
dp 布尔、nums[i]。
为什么正确
0/1 背包 dp[sum] 可达;等价 subset sum。
不变量
dp[j]|=dp[j-num]。
面试怎么说
0/1 背包 O(n·sum)。
人类输入
nums=[1,5,11,5] 能否平分 sum=22→子集和 11。
机制
0/1 背包 dp[sum] 可达;等价 subset sum。
机器状态
dp 布尔、nums[i]。
可观察结果
可达 11,true。
不变量
- · dp[j]|=dp[j-num]。
常见误区
- · sum 奇数直接 false。
迁移练习
- · LC494 目标和
- · LC322 零钱
面试怎么答
0/1 背包 O(n·sum)。