esc to dismiss

416. 分割等和子集

题目

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

示例 1:

输入:nums = [1,5,11,5]

输出:true

解释:数组可以分割成 [1, 5, 5][11]

示例 2:

输入:nums = [1,2,3,5]

输出:false

解释:数组不能分割成两个元素和相等的子集。

解体思路

这道题目是 动态规划 ,不过要难一些

这道题有点像 0-1背包问题(背包问题 )。

分成两个子集,并且和相等,那么输入数组的总和得是偶数,否则就无法分割。以总和的一半为目标值(target).

以下来自于 LeeCode 一位网友的解答:

状态与状态转移方程

状态定义:

dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数,每个数只能用一次,使得这些数的和恰好等于 j。

状态转移方程:

很多时候,状态转移方程思考的角度是「分类讨论」,对于「0-1 背包问题」而言就是「当前考虑到的数字选与不选」。

  • 不选择 nums[i],如果在 [0, i - 1] 这个子区间内已经有一部分元素,使得它们的和为 j ,那么 dp[i][j] = true;

  • 选择 nums[i],如果在 [0, i - 1] 这个子区间内就得找到一部分元素,使得它们的和为 j - nums[i]。

因此得到 状态转移方程:

dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]

作者:liweiwei1419

链接:https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/0-1-bei-bao-wen-ti-xiang-jie-zhen-dui-ben-ti-de-yo/

画一张二维的dp表(为了看上去更清晰,我把表中的 false 以 x 代替)

+-------------+------+------+---+---+---+------+------+---+---+---+------+------+

| / | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |

+-------------+------+------+---+---+---+------+------+---+---+---+------+------+

| nums[[0]] | true | true | x | x | x | x | x | x | x | x | x | x |

| nums[[1]] | true | true | x | x | x | true | true | x | x | x | x | x |

| nums[[2]] | true | true | x | x | x | true | true | x | x | x | x | true |

| nums[[3]] | true | true | x | x | x | true | true | x | x | x | true | true |

+-------------+------+------+---+---+---+------+------+---+---+---+------+------+

经验教训

...

x