Comment on page

# 416.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:
Each of the array element will not exceed 100.
The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

## 代码

### Approach #1 DFS

class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num: nums) sum += num;
if ((sum & 1) > 0) return false;
return dfs(nums, 0, sum >> 1);
}
private boolean dfs(int[] nums, int s, int target) {
if (target < 0 || (s >= nums.length)) return false;
if (target == 0 || dfs(nums, s, target - nums[s])
|| dfs(nums, s + 1, target)) return true;
return false;
}
}

### Approach #2 Dyanamic Programming knapsack

public boolean canPartition(int[] nums) {
if (nums == null || nums.length == 0) return true;
int sum = Arrays.stream(nums).sum();
if ((sum & 1) == 1) return false;
sum /= 2;
int n = nums.length;
boolean[] dp = new boolean[sum+1];
Arrays.fill(dp, false);
dp[0] = true;
for (int num : nums) {
for (int i = sum; i > 0; i--) {
if (i >= num) {
dp[i] = dp[i] || dp[i-num];
}
}
}
return dp[sum];
}