leetcode-416

题目

https://leetcode.cn/problems/partition-equal-subset-sum/?envType=daily-question&envId=2025-04-07

分析

• 题干很简单，要求把数字分割成两个子集（子集不为空，其他无限制）两个子集和要相同
• 考虑 dfs 或者 dp(0-1背包)
  • dfs 复杂度太高，放弃
• 0-1背包解法
  • dp[i][j] 0-i个数范围内，可以凑出j
  • dp[i][j] =
    • dp[i-1][j] + dp[i-1][j-nums[i]] （j >= nums[i]）
    • dp[i-1][j] （j< nums[i]）

源代码

https://github.com/Norton-Lin/algorithm/blob/master/go/src/leetcode_416/2025_04_07_416.go