力扣hot100：416.分割等和子集（组合/动态规划/STL问题）

组合数问题

我们思考一下，如果要把数组分割成两个子集，并且两个子集的元素和相等，是否等价于在数组中寻找若干个数使之和等于所有数的一半？是的！

因此我们可以想到，两种方式：

①回溯的方式找到target，但是回溯是阶乘级别的算法，这里会超时。

②从前往后遍历，形象说明：定义n个集合dp[i]，dp[i]表示前i个数的可能组合值，则有dp[i]={dp[i-1],dp[i-1]+i}，dp[i-1]+i指的是i加上dp[i-1]中的所有元素得到的集合。同时由于长度最长200，数值最大为100，因此数的范围最大为1<=i<=20000，因此最多只有20000个不同的数。因此dp最大为2W个数！所以我们可以用集合实现，并且时间复杂度满足要求O(nums.length*nums.length*max(nums[i]))！

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(auto &i:nums) sum+=i;
        if(sum&1||nums.size()==1) return false;//只有偶数总和可以
        sum>>=1;
        unordered_set<int> Set;
        vector<int> temp;
        for(auto &i:nums){
            if(i==sum) return true;
            for(auto it=Set.cbegin();it!=Set.cend();++it){
                int cur=*it+i;
                if(cur==sum) return true;
                if(cur<sum) temp.emplace_back(cur);//＞sum的没意义
            }
            for(auto & j:temp) Set.insert(j);
            temp.clear();
            Set.insert(i);
        }
        return false;
    }
};

遇到的问题：

        在循环遍历的过程中往容器中插入元素会导致容器迭代器end()和size()，时刻发生变化。与此同时，有的容器比如vector和string，往后面增加元素超过容量capacity可能会导致拷贝，从而整个迭代器失效。因此！在使用循环并且需要添加元素时，想使用迭代器需要额外注意！

比如本题是先将所需增加的放入到一个vector中的。

我们不能企图使用临时“指针”迭代器i=end()，然后遍历到it!=i，这是错误的！因为end()可能失效，而不是end()当时指向的位置。以下是C++ prime中特地提到的（这么小，但又特别灾难的坑被遇到了）

int tmp=Set.size();
for(auto it=Set.cbegin();tmp!=0;++it,--tmp){ 
    int cur=*it+i;
    if(cur==sum) return true;
    temp.emplace_back(cur);
    Set.insert(cur);
}

这样做仍然是错误的，实际上我们在往非顺序容器中插入元素时，容器的数据结构会发生变化，因此导致++it可能并非按照原来的想法遍历，所以是错误的！

唯一正确且安全的方式是，如果需要在遍历的时候同时添加元素，最好不要使用迭代器！迭代器可以很好的遍历元素或者按迭代器范围赋值。但是边添加边遍历问题非常大。

因此对于无序容器只能使用迭代器的情况下，使用临时容器存储是非常必要的；对于顺序容器可以使用下标的情况下，使用下标更好。

动态规划

        这道题实际上和0-1背包问题很像，即从n个物品中拿出一部分使得其值刚好等于target。意识到这一点我们可以定义动态转移方程：

dp[i][k]=max(dp[i-1][k-nums[i]],dp[i-1][k]);

dp[0][nums[0]]=1;

//dp[i][k]表示拿前i个物品是否可以达到重量k。

        这实际上和方法一组合数问题是异曲同工的，方法一使用集合实现，那么如果方法一使用的是数组实现呢？那么数组中标记为1的实际上就是方法二的状态了！

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(auto &i:nums) sum+=i;
        if(sum&1||nums.size()==1) return false;
        sum>>=1;
        vector<vector<int>> dp(nums.size(),vector<int>(sum+1,0));//超过sum实际上就不用看了
        if(nums[0]<=sum)
            dp[0][nums[0]]=1;
        for(int i=1;i<nums.size();++i){
            for(int j=1;j<=sum;++j){
                dp[i][j]=dp[i-1][j];
                if(j-nums[i]>=0)
                    dp[i][j]=max(dp[i-1][j-nums[i]],dp[i-1][j]);
            }
            if(nums[i]<=sum)
                dp[i][nums[i]]=1;
        }
        return dp[nums.size()-1][sum];
    }
};

由于只用到前面的值，很显然我们可以降维优化。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(auto &i:nums) sum+=i;
        if(sum&1||nums.size()==1) return false;
        sum>>=1;
        vector<int> dp(sum+1,0);//超过sum实际上就不用看了
        if(nums[0]<=sum)
            dp[nums[0]]=1;
        for(int i=1;i<nums.size();++i){
            for(int j=sum;j>=nums[i];--j){
                dp[j]=max(dp[j],dp[j-nums[i]]);
            }
        }
        return dp[sum];
    }
};