首页 > 代码库 > [LeetCode] Partition Equal Subset Sum 相同子集和分割

[LeetCode] Partition Equal Subset Sum 相同子集和分割

 

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:
Both the array size and each of the array element will not exceed 100.

Example 1:

Input: [1, 5, 11, 5]Output: trueExplanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]Output: falseExplanation: The array cannot be partitioned into equal sum subsets.

 

这道题给了我们一个数组,问我们这个数组能不能分成两个非空子集合,使得两个子集合的元素之和相同。那么我们想,原数组所有数字和一定是偶数,不然根本无法拆成两个和相同的子集合,那么我们只需要算出原数组的数字之和,然后除以2,就是我们的target,那么问题就转换为能不能找到一个非空子集合,使得其数字之和为target。开始我想的是遍历所有子集合,算和,但是这种方法无法通过OJ的大数据集合。于是乎,动态规划DP就是我们的不二之选。我们定义一个一维的dp数组,其中dp[i]表示数字i是否是原数组的任意个子集合之和,那么我们我们最后只需要返回dp[target]就行了。我们初始化dp[0]为true,由于题目中限制了所有数字为正数,那么我们就不用担心会出现和为0或者负数的情况。那么关键问题就是要找出递归公式了,我们需要遍历原数组中的数字,对于遍历到的每个数字nums[i],我们需要更新我们的dp数组,要更新[nums[i], target]之间的值,那么对于这个区间中的任意一个数字j,如果dp[j - nums[j]]为true的话,那么dp[j]就一定为true,于是地推公式如下:

dp[j] = dp[j] || dp[j - nums[i]]         (nums[i] <= j <= target)

有了递推公式,那么我们就可以写出代码如下:

 

解法一:

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

 

这道题还可以用bitset来做,感觉也十分的巧妙,

 

解法二:

class Solution {public:    bool canPartition(vector<int>& nums) {        bitset<5001> bits(1);        int sum = accumulate(nums.begin(), nums.end(), 0);        for (int num : nums) bits |= bits << num;        return (sum % 2 == 0) && bits[sum >> 1];    }};

 

参考资料:

https://discuss.leetcode.com/topic/62334/simple-c-4-line-solution-using-a-bitset

https://discuss.leetcode.com/topic/62312/java-solution-similar-to-backpack-problem-easy-to-understand/2

 

LeetCode All in One 题目讲解汇总(持续更新中...)

[LeetCode] Partition Equal Subset Sum 相同子集和分割