2024每日刷题(172)
Leetcode—416. 分割等和子集
C++实现代码
class Solution {
public:bool canPartition(vector<int>& nums) {int sum = accumulate(nums.begin(), nums.end(), 0);if(sum % 2) {return false;}int m = nums.size();int subSum = sum / 2;int n = subSum;vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));dp[0][0] = true;for(int i = 1; i <= m; i++) {for(int j = 0; j <= n; j++) {dp[i][j] = dp[i - 1][j];if(j >= nums[i - 1]) {dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];}}}return dp[m][n];}
};
// 0 1 2 3 4
// T F F F F
// 1 T T F F F
// 2 T T T F F
// 5 T
运行结果
之后我会持续更新,如果喜欢我的文章,请记得一键三连哦,点赞关注收藏,你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 !!!↖(▔▽▔)↗感谢支持!