LeetCode [416] Partition Equal Subset Sum

 416. Partition Equal Subset Sum

Medium

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:

1. Each of the array element will not exceed 100.
2. 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution { public boolean canPartition(int[] nums) { int s = 0; for(int i: nums) s += i; if(s%2==1) return false; s = s/2; int n = nums.length; int dp[][] = new int[n+1][s+1]; dp[0][0] = 1; for(int i=1; i<=n; ++i){ for(int j=1; j<=s; ++j){ dp[i][j] = dp[i-1][j]; if(j>=nums[i-1]){ dp[i][j] |= dp[i-1][j-nums[i-1]]; } } } return dp[n][s]==1; } }