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;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/228732.html
標籤：其他
上一篇：四數相加 II
下一篇：并查集-Java實作