LeetCode 416 分割等和子集

416.分割等和子集

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

示例：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

动态规划

此处是集合的划分，要求划分的两个集合中元素的和相等。此处可以将问题转化为两个背包，并且两个背包的容量相同，都等于集合中全部元素总和的一半。那么子集划分的过程，也就是向背包中放入相应元素的过程，若是能将一个背包装满，那么另外一个也就一定能够装满。首先求得集合中全部元素的总和 2n 。

1. 动态规划数组的定义：初始的 dp[i] 表示在元素 0-0 中，背包容量为 i 时，能否恰好将背包装满。能够装满则为 true 不能为 false

2. 动态规划数组的推导：在第 i 次迭代时，在元素 0-i 中进行选择，此处仅有两种情况，选取元素 i 或者不选取元素 i 。那么 dp[j]=dp[j-nums[i]]||dp[j]

3. 动态规划数组的初始化：在初始时，dp[i] 表示在元素 0-0 中，背包容量为 i 时，能否恰好将背包装满。那么先全部初始化为 false ，若是 nums[0]<=n 则令 dp[nums[0]]=true ，并且对于背包容量为 0 时，本身就是满的，因此 dp[0]=true;

4. 动态规划数据的遍历顺序：外层循环，是对元素个数进行遍历，不断增加可以放入背包的元素数量，从 i=1,...,nums.size()-1 进行遍历，内层循环是对 dp 数据进行遍历，并且dp数组的遍历过程是从右向左进行的。并且在遍历的过程中只要出现 dp[n]==true 即可提前结束循环。

5. 举例验证：对于 nums = [1,5,11,5] 那么 dp 数组的长度为 12 初始化为 dp[1]=true 其他都为 false ，然后开始循环，第一遍循环： dp={1,1,0,0,0,1,1,0,0,0,0,0} ，第二遍循环 dp={1,1,0,0,0,1,1,0,0,0,0,1} 循环提前结束，验证正确。

代码实现：

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