Partition Equal Subset Sum (M)
题目
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 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 <= 2001 <= nums[i] <= 100
题意
在一个给定数组中找到一个子数组，使其和为指定值。
思路
使用记忆化搜索容易实现。
代码实现
Java
class Solution {
public boolean canPartition(int[] nums) {
int total = 0;
int left = 0, right = nums.length - 1;
for (int num : nums) {
total += num;
}
if (total % 2 == 1) {
return false;
}
return dfs(total / 2, nums, 0, new Boolean[total / 2 + 1][nums.length]);
}
private boolean dfs(int sum, int[] nums, int start, Boolean[][] record) {
if (start == nums.length) {
return sum == 0;
}
if (sum < 0) {
return false;
}
if (record[sum][start] != null) {
return record[sum][start];
}
boolean found = dfs(sum, nums, start + 1, record) || dfs(sum - nums[start], nums, start + 1, record);
record[sum][start] = found;
return found;
}
}
```# Partition Equal Subset Sum (M)
## 题目
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 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`
---
## 题意
在一个给定数组中找到一个子数组，使其和为指定值。
## 思路
使用记忆化搜索容易实现。
---
## 代码实现
### Java
```java
class Solution {
public boolean canPartition(int[] nums) {
int total = 0;
int left = 0, right = nums.length - 1;
for (int num : nums) {
total += num;
}
if (total % 2 == 1) {
return false;
}
return dfs(total / 2, nums, 0, new Boolean[total / 2 + 1][nums.length]);
}
private boolean dfs(int sum, int[] nums, int start, Boolean[][] record) {
if (start == nums.length) {
return sum == 0;
}
if (sum < 0) {
return false;
}
if (record[sum][start] != null) {
return record[sum][start];
}
boolean found = dfs(sum, nums, start + 1, record) || dfs(sum - nums[start], nums, start + 1, record);
record[sum][start] = found;
return found;
}
}