Leetcode Hot100 第30题 416.分割等和子集

class Solution {
public:bool canPartition(vector<int>& nums) {int sum=0;for(int num:nums){sum+=num;}if(sum%2==1) return false;int bag_size = sum/2;// return dfs(nums,nums.size()-1,bag_size);//递归做法vector<vector<bool>> dp(nums.size()+1,vector<bool>(bag_size+1));dp[0][0]=true;for(int i=1;i<=nums.size();i++){for(int j=0;j<=bag_size;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[nums.size()][bag_size];}bool dfs(vector<int>& nums, int i, int target){if(i<0) return target==0? true: false;if(target==0) return true;if(target<0) return false;return dfs(nums,i-1,target-nums[i])||dfs(nums,i-1,target);}
};