Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- bool canPartition(vector<int>& nums) {
- int sm = accumulate(nums.begin(), nums.end(),0);
- if(sm&1)return 0;
- sm/=2;
- int n = nums.size();
- vector<vector<int>>dp(n+1, vector<int>(sm+1, -1));
- return f(nums, 0, sm, dp);
- }
- bool f(vector<int>&nums, int id, int target, vector<vector<int>>&dp)
- {
- if(target == 0)
- return true;
- if(target<0 || id == nums.size())
- {
- return false;
- }
- if(dp[id][target]!=-1)return dp[id][target];
- bool res = f(nums, id+1, target, dp) | f(nums, id+1, target - nums[id], dp);
- return dp[id][target] = res;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement