分割等和子集

分割等子集

题目难易：中等

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

注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200

示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2: 输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集.

提示：

1 <= nums.length <= 200

1 <= nums[i] <= 1

这道题对我来说是一道比较难得动态规划题，难在哪呢？看完题你会发现是很懵的，如果不是在动态规划题组里的题，我根本就不会想用动态规划去做这道题，好了现在知道是动态规划的题了，结果发现还是没有思路，完全看不出来要怎么用动态规划，结果最后还是看题解给弄出来了。

看完题解发现这道题是可以转变为01背包的问题的，为什么呢？

1.背包的体积为：num/2（num等于数组所有元素的和）

2.数组的元素可以转换为各种的物品，这里需要注意的是物品的重量和价值都是该元素的数值（这里不懂的话可以先看下面，下面会再次说道这个）

3.背包的容量转换为了拆分过后数组里的元素总和

4.数组中的元素只能取一次

所以我们试一试01背包的思路

这里还是需要动态规划做题的五大步骤

1.确定dp数组以及下标含义

dp[i][j]表示从下标为（0~i）的物品中任意取，放入容量为j的背包，价值总和的最大值

那么这道题的含义推过来就是

从下标（0~i）的元素任意取，放入容量为j的背包，价值总和的最大值，那么当j=num/2时，这个dp[i][j]只要等于num/2，就是可以拆分，否则就不行。（这里理解起来比较困难，可以捋一捋因为我前面说了这道题比较特殊，这道题物品的重量和价值是相等的，所以在容量j=num/2的背包中价值最大也就是num/2，而这个价值就是背包中元素的和，既然元素的和能等于num/2的话，那么必然是可以拆分的）

2.确定递推公式

这段代码是01背包问题的递推公式

dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])

那么在这道题中又有什么变化呢

整体当然是不变的，毕竟还是用的01背包问题的思想，但是要注意的是在这道题中weight[i]=value[i]=nums[i],所以这道题就需要进行相应转换

3.dp数组如何初始化

从递推公式中可以看到i是由i-1推出的，所以i=0必须进行初始化

当 i=0时当能装下时dp[0][j]=nums[0]，当装不下时的dp[0][j]=0

当j=0时初始化显然dp[i][0]=0

4.确定遍历顺序

从（1,1）从左到右从上到下进行遍历

5.举例推导dp数组

这个可以写，也可以不写，因为这一步是验证前面思考是否正确的

整体代码