题意

给一个非负数组，问能否把数组分成两部分，让两部分的和相等

限制：

数组长度不大于200

数组的每个值不大于100

方法

递推

要让分割的两部分和相等，也就是其中一部分的和等于整个数组的和的一半。

那么可以考虑去求一部分数组能达成哪些和

考虑用aval[i][j]=true/false表示，前i个值，能否选取一部分，使得它们的和为j

那么如果aval[i][j]可行，对于第i+1个值，分别是选择第i+1个值和不选择它两种方案。

不选择时aval[i+1][j] = true

选择时aval[i+1][j+nums[i+1]] = true

最后只需要检查aval[最后一个位置][sum/2] 是否可达即可

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return bool布尔型
     */
    bool partition(vector<int>& nums) {
        // write code here
        int s = 0;
        for(int i = 0;i<nums.size();i++){
            s+=nums[i];
        }
        if(s%2)return false; // 奇数
        vector<vector<int> > aval(nums.size()+1,vector<int>(s+1,0));
        aval[0][0] = true;
        for(int i = 0;i<nums.size();i++){ // 枚举每个位置
            for(int v = 0;v<=s;v++){ // 枚举每个值
                if(!aval[i][v])continue; // 不可达
                aval[i+1][v] = true; // 不选择
                aval[i+1][v+nums[i]] = true; // 选择
            }
        }
        return aval[nums.size()][s/2];
    }
};

复杂度分析

令总和的大小为$ss$

时间复杂度: 因为对于每个位置，尝试了所有小于和的值，每次找到可行值，会更新两个值，所以总的时间复杂度为$O(n\cdot s)O(n\backslash cdot\; s)$

空间复杂度: 主要消耗在状态的记录，所以和状态大小相关，空间复杂度为$O(n\cdot s)O(n\backslash cdot\; s)$

基于滚动数组的空间优化

按照上面的方法，以题目样例[1,5,11,5]为例

其中11能达到，所以输出为可行

但根据转移关系来看，如果前面能达到的值，后面一定能达到，考虑复用数组。

如果直接按照原有代码改成一维数组，会产生新的问题：当值为1时，因为0可达，所以更新了1可达。而又遍历到1时，发现可达，又会更新2是可达的，但实际上这样相当于加了两次1，并不满足题意。

注意到更新的值一定比原来的值大，所以考虑反向遍历，这样每次更新的值的来源的值更小，那么来源的值一定是更新前的值。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return bool布尔型
     */
    bool partition(vector<int>& nums) {
        // write code here
        int s = 0;
        for(int i = 0;i<nums.size();i++){
            s+=nums[i];
        }
        if(s%2)return false; // 奇数
        vector<int> aval(s+1,0); // 复用数组
        aval[0] = true;
        for(int i = 0;i<nums.size();i++){ // 枚举每个位置
            for(int v = s;v>=0 ;v--){ // 逆序枚举
                if(!aval[v])continue; // 不可达
                aval[v+nums[i]] = true; // 因为复用，只用更新变化
            }
        }
        return aval[s/2];
    }
};

复杂度分析

时间复杂度: 因为对于每个位置，尝试了所有小于和的值，每次找到可行值，会更新一个值，虽然空间做了压缩，但时间上还是相同的代价，所以总的时间复杂度为$O(n\cdot s)O(n\backslash cdot\; s)$

空间复杂度: 主要消耗在状态的记录，所以和状态大小相关，空间复杂度为$O(s)O(s)$