1. 題目

給定一個只包含正整數(shù)的非空數(shù)組。
是否可以將這個數(shù)組分割成兩個子集，使得兩個子集的元素和相等。

注意:
每個數(shù)組中的元素不會超過 100
數(shù)組的大小不會超過 200

示例 1: 輸入: [1, 5, 11, 5] 輸出: true 解釋: 數(shù)組可以分割成 [1, 5, 5] 和 [11].示例 2: 輸入: [1, 2, 3, 5] 輸出: false 解釋: 數(shù)組不能分割成兩個元素和相等的子集.

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/partition-equal-subset-sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

類似題目：LeetCode 698. 劃分為k個相等的子集（回溯）

• 每個元素取或者不取，動態(tài)規(guī)劃，求解所有可能的和情況

class Solution { public:bool canPartition(vector<int>& nums) {if(nums.size() <= 1)return false;int sum = 0, i, j;for(i = 0 ; i < nums.size(); ++i)sum += nums[i];if(sum&1) return false;//奇數(shù)不可分//dp求解，每個元素拿或者不拿，求解所有的狀態(tài)set<int> state;state.insert(0);//初始化state.insert(nums[0]);for(i = 1; i < nums.size(); ++i){for(auto it = state.rbegin(); it != state.rend(); ++it){ //用set，不能用哈希set，且必須逆序遍歷，新插入的不會被本次遍歷到state.insert(*it+nums[i]);}if(state.count(sum>>1))return true;}return false;} };

936 ms 16.3 MB

• 采用數(shù)組實現(xiàn)dp

class Solution { public:bool canPartition(vector<int>& nums) {if(nums.size() <= 1)return false;int sum = 0, i, j;for(i = 0 ; i < nums.size(); ++i)sum += nums[i];if(sum&1) return false;//奇數(shù)不可分//dp求解，每個元素拿或者不拿，求解所有的狀態(tài)vector<bool> state(sum+1, false);state[0] = true;//初始化state[nums[0]] = true;for(i = 1; i < nums.size(); ++i){for(j = sum; j >= 0; --j){ if(state[j])state[j+nums[i]] = true;}if(state[sum>>1])return true;}return false;} };

312 ms 8.9 MB

• 再優(yōu)化下存儲空間，只查找到 sum/2 的狀態(tài)，超過的忽略
• 以下代碼有bug [99,1] 這個例子，第一個數(shù)會越界

class Solution { public:bool canPartition(vector<int>& nums) {if(nums.size() <= 1)return false;int sum = 0, i, j;for(i = 0 ; i < nums.size(); ++i)sum += nums[i];if(sum&1) return false;//奇數(shù)不可分//dp求解，每個元素拿或者不拿，求解所有的狀態(tài)sum >>= 1;vector<bool> state(sum+1, false);state[0] = true;//初始化state[nums[0]] = true;for(i = 1; i < nums.size(); ++i){for(j = sum; j >= 0; --j){ if(state[j] && j+nums[i] <= sum)state[j+nums[i]] = true;}if(state[sum])return true;}return false;} };

164 ms 8.8 MB

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。