原题地址

https://leetcode.com/problems/partition-equal-subset-sum/description/

题意

给一个非空数组，把数组划分成和相同的两部分

思路

对数组求和，若是奇数返回false，若是偶数自底向上建表
做的时候遇到的问题：一开始建表忘记先全都置成false了

代码

class Solution {
public:
    int Sum(vector<int> & nums){
        int result=0;
        for(int i =0;i<nums.size();i++){
            result+=nums[i];
        }
        return result;
    }
    
    bool canPartition(vector<int>& nums) {
        int sum = Sum(nums);
        if(sum%2!=0){
            return false;
        }
        int target = sum/2;
        int n = nums.size();
        bool dp[target+1][n+1];
        memset(dp,false,sizeof(bool)*(target+1)*(n+1));
        for(int i =0;i<=n;i++){
            dp[0][i]=true;
        }
        for(int i =1;i<=target;i++){
            dp[i][0]=false;
        }
        for(int i =1;i<=target;i++){
            for(int j =1;j<=n;j++){
                if(i>=nums[j-1]){
                    dp[i][j]= dp[i-nums[j-1]][j-1];
                }
                if(dp[i][j]){
                    for(int k =j+1;k<=n;k++){
                        dp[i][k]=true;
                    }
                    break;
                }
                
            }
        }
        return dp[target][n]; 
    }
};