# 416.Partition-Equal-Subset-Sum

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/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];
}``````

Last updated