416 Partition Equal Subset Sum 分割等和子集
Description:
Given a non-empty array nums 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.
Example:
Example 1:
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
Constraints:
1 <= nums.length <= 200
1 <= nums[i] <= 100
題目描述:
給定一個只包含正整數(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ù)組不能分割成兩個元素和相等的子集.
思路:
動態(tài)規(guī)劃
dp[i][j] 表示在 [0, i]區(qū)間中是否能選出一些 nums數(shù)組中的值, 使得這些元素和等于 j
dp[0][j] 應(yīng)該初始化為 nums[k] == j, 其中 0 <= k <= len(nums) - 1
從題意可得, sum(num)必須為偶數(shù), 只要求得 dp[len(nums) - 1][sum(nums) / 2]即可
dp[i][j]可以分為兩個部分, 要么不取 nums[i], 要么取 nums[i]
轉(zhuǎn)移方程 dp[i][j] = dp[i - 1][j] || dp[i][sum(nums) / 2 - nums[i]]
可以看出來只需要記錄一行 dp變量, 壓縮空間復(fù)雜度到 O(sum(nums))
時間復(fù)雜度O(nsum(nums)), 空間復(fù)雜度O(sum(nums))
代碼:
C++:
class Solution
{
public:
bool canPartition(vector<int>& nums)
{
int sum = accumulate(nums.begin(), nums.end(), 0), n = nums.size();
if (sum & 1) return false;
vector<bool> dp((sum >>= 1) + 1);
for (int i = 0; i < n; i++) for (int j = sum; j > nums[i] - 1; j--)
{
if (!i) dp[j] = (nums[i] == j);
else dp[j] = dp[j] or dp[j - nums[i]];
}
return dp.back();
}
};
Java:
class Solution {
public boolean canPartition(int[] nums) {
int s = 0, n = nums.length;
for (int num : nums) s += num;
if ((s & 1) != 0) return false;
s >>= 1;
boolean dp[] = new boolean[s + 1];
for (int i = 0; i < n; i++) for (int j = s; j > nums[i] - 1; j--) {
if (i == 0) dp[j] = (j == nums[i]);
else dp[j] = dp[j] || dp[j - nums[i]];
}
return dp[s];
}
}
Python:
class Solution:
def canPartition(self, nums: List[int]) -> bool:
return 1 - (sum(nums) & 1) == reduce(lambda x, y: x | (x << y), nums, 1) >> (sum(nums) >> 1) & 1
