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

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.

首先看到这道题的时候，我也是一点思路都没有。通过看别人（大神）的代码，然后看很长时间。。。思考很长时间，，，才弄懂。我相信时间会证明一切！！！

背包问题：有一个容量为 V 的背包，和一些物品。这些物品分别有两个属性，体积 w 和价值 v，每种物品只有一个。要求用这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。
这个问题可以和背包问题相比，使用动态规划。

思路：

首先，数组可以等分，不能是奇数，只能是偶数，然后sum是数组的元素和。然后每个元素相当于一件物品，sum/2相当于背包的容量。只要背包可以装满，就相当于数组可以等分。
最关键的代码：
len为数组长度，sum为数组元素和。dp[ i ][ j ]的意思是：前i个物品是否可以等于j。（前i个物品可以装入也可以不装入，1,5,11,5其中前三个物品就可以达到1和6）

for(int i=1;i<=len;i++){//每一个元素
            for(int j=1;j<=sum/2;j++){//背包容量
                if(j-nums[i-1]<0){//j不可以装入该物品，则dp[i][j]等于上一个dp的值
                    dp[i][j] = dp[i-1][j];
                }else{//不装入或者装入，有点难解释。。。如果上一层是true，这一层一定是true。。。进入else的时候应该是j==nums[i-1]，而且dp[i-1][0]==true。。。希望多读几遍完整代码。。
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
                }
            }
        }

动态规划有点难理解，但是只要坚持有就希望，大脑需要不断的强化练习，才能有更深的记忆，我一定不会放弃。
完整代码：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) return false;
		int sum = 0;
		for (int n : nums)
			sum += n;
		if (sum % 2 == 1) return false;
        vector<vector<bool>>dp(len+1,vector<bool>(sum/2 + 1,false));
        for(int i=0;i<len+1;i++){
            dp[i][0] = true;
        }
        for(int i=1;i<=len;i++){
            for(int j=1;j<=sum/2;j++){
                if(j-nums[i-1]<0){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j]||dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[len][sum/2];
    }
};

一个集坚强与自信于一身的菇凉。