描述

416. 分割等和子集
給你一個 只包含正整數 的 非空 數組 nums 。請你判斷是否可以將這個數組分割成兩個子集，使得兩個子集的元素和相等。

示例 1：

輸入：nums = [1,5,11,5]
輸出：true
解釋：數組可以分割成 [1, 5, 5] 和 [11] 。
示例 2：

輸入：nums = [1,2,3,5]
輸出：false
解釋：數組不能分割成兩個元素和相等的子集。

思路一：動態規劃

使用01背包的思路解

class Solution { public:bool canPartition(vector<int>& nums) {if(nums.size()==0) return false;int sum=0,target=0;; //由于數組總數一樣，只要找到sum/2就算可以找到了子集for(int i=0;i<nums.size();i++){sum+=nums[i];}if(sum%2 == 1) return false; //當不能被2整除就返回為假target = sum/2; //01背包問題,目標值為背包的容量vector<int> dp(target+1,0); //初始化dp[i],i代表的是背包的容量,dp[i]代表的是i容量下最大值//開始01背包for(int i=0;i<nums.size();i++){for(int j=target;j>=nums[i];j--){dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);}}if(dp[target] == target) return true;return false;} };

9.26 二刷代碼記錄

class Solution { public:bool canPartition(vector<int>& nums) {//轉換為01背包問題,找到整個數組sum的一半//求容器總和int sum = accumulate(nums.begin(),nums.end(),0);if(sum%2==1) return false; //當為奇數時候不可能等分兩半，所以不可能找到int target = sum/2; //當為偶數時候等分，目標值為總數的一半，即背包容量int n = nums.size();// dp[i]中的i表示背包內總和// 題目中說：每個數組中的元素不會超過 100，數組的大小不會超過 200// 總和不會大于20000，背包最大只需要其中一半，所以10001大小就可以了vector<int> dp(10001,0);//初始化//開始01背包for(int i=0;i<n;i++){for(int j=target;j>=nums[i];j--){dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);}}if(dp[target] == target) return true;return false;} };

總結

以上是生活随笔為你收集整理的LeetCode-动态规划背包题-416. 分割等和子集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。