代码随想录算法训练营第四十二天| 416 分割等和子集

目录

416 分割等和子集

---

416 分割等和子集

class Solution {
public:const int N = 210;bool canPartition(vector<int>& nums) {vector<int>f(N);int sum = 0;for(auto num : nums)sum += num;if(sum % 2 == 1)return false;//如果int target = sum / 2;for(int i = 0;i < nums.size();i++){for(int j = target;j >= nums[i];j--){f[j] = max(f[j],f[j - nums[i]] + nums[i]);}}if(f[target] == target)return true;return true;}
};

时间复杂度O(n×target)

空号复杂度O(n)