Partition Equal Subset Sum（C++分割等和子集）

青旅半醒 2022-09-08 04:59 92阅读 0赞

（1）dp，背包问题

class Solution {
    public:
        bool canPartition(vector<int>& nums) {
            int n = nums.size();
            if (n < 2) {
                return false;
            }
            int sum = accumulate(nums.begin(), nums.end(), 0);
            int maxNum = *max_element(nums.begin(), nums.end());
            if (sum & 1) {
                return false;
            }
            int target = sum / 2;
            if (maxNum > target) {
                return false;
            }
            vector<vector<int>> dp(target+1, vector<int>(n, 0));
            for (int i = 0; i < n; i++) {
                dp[0][i] = true;
            }
            dp[nums[0]][0] = true;
            for (int i = 1; i <= target; i++) {
                for (int j = 1; j < n; j++) {
                    if (i >= nums[j]) {
                        dp[i][j] = dp[i][j-1] || dp[i-nums[j]][j-1];
                    } else {
                        dp[i][j] = dp[i][j-1];
                    }
                }
            }
            return dp[target][n-1];
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，92人围观）

还没有评论，来说两句吧...

相关阅读

相关 416. 分割等和子集

给你一个只包含正整数的非空数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

た入场券/ 2024年05月24日 01:37/ 0 赞/ 39 阅读

相关 LeetCode 416：分割等和子集（子集背包）

[链接][Link 1] 题目： ![在这里插入图片描述][382c34bedb7f4ae4b9c23d17565b38e0.png] 方法：子集背包思路：

╰+哭是因爲堅強的太久メ/ 2024年04月07日 14:13/ 0 赞/ 41 阅读

相关 LeetCode-416. 分割等和子集

目录题目分析回溯法动态规划动态规划(压缩) 题目来源 [416. 分割等和子集][416.] 题目

比眉伴天荒/ 2024年03月26日 20:18/ 0 赞/ 47 阅读

相关 416. 分割等和子集

打卡!!!每日一题今天带着大家做一道相对比较难的题目，当然我会通过讲解01背包问题带着大家过渡一下。题目描述： > 给你一个只包含正整数的非空数组 nums

以你之姓@/ 2023年10月11日 18:18/ 0 赞/ 93 阅读

相关 416. 分割等和子集

题目： [416. 分割等和子集][416.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_t

ゝ一世哀愁。/ 2022年12月01日 15:43/ 0 赞/ 125 阅读

相关 leetcode 416 分割等和子集

前言题目：[416. 分割等和子集][416.] 参考题解：[分割等和子集-代码随想录][-] -------------------- 提交代码核心思路

川长思鸟来/ 2022年09月16日 08:40/ 0 赞/ 108 阅读

相关 Partition Equal Subset Sum（C++分割等和子集）

（1）dp，背包问题 class Solution { public: bool canPartition(vector<int>& n

青旅半醒/ 2022年09月08日 04:59/ 0 赞/ 93 阅读

相关 leetcode 416. Partition Equal Subset Sum | 416. 分割等和子集（Java）

题目 [https://leetcode.com/problems/partition-equal-subset-sum/][https_leetcode.com_pro

你的名字/ 2022年09月02日 11:55/ 0 赞/ 120 阅读

相关 [Leetcode][python]Subsets/Subsets II/子集/子集 II

Subsets 题目大意给定一个由不同数字组成的集合，罗列出该集合的所有子集。解题思路见下方代码代码纯思路参考： [https

布满荆棘的人生/ 2022年06月07日 12:19/ 0 赞/ 163 阅读

相关 leetcode416. Partition Equal Subset Sum

题目要求 Given a non-empty array containing only positive integers, find if the array

太过爱你忘了你带给我的痛/ 2022年03月08日 13:26/ 0 赞/ 152 阅读