LeetcodeHot100第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); } };