0-1背包

LeetCode 416 https://leetcode.cn/problems/partition-equal-subset-sum/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题相当于能否从 nums 中选出一个子序列，其元素和恰好等于 s/2。这是 0-1 背包的恰好装满型问题。 dfs(i, j)=dfs(i−1, j−nums[i]) || dfs(i−1, j) ​ 时间复杂度：O(ns)，其中 n 是 nums 的长度，s 是 nums 的元素和（的一半）。由于每个状态只会计算一次，动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。本题状态个数等于 O(ns)，单个状态的计算时间为 O(1)，所以动态规划的时间复杂度为 O(ns)。 空间复杂度：O(ns)。保存多少状态，就需要多少空间。 ...