416. Partition Equal Subset Sum

Question

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.

Solution:

  • Method 1: dp 01KnapSack 
      class Solution {
      public boolean canPartition(int[] nums) {
          int len = nums.length;
          int sum = 0;
          for(int num : nums)
              sum += num;
          if((sum & 1) == 1) return false;
          sum >>= 1;
          boolean[][] dp = new boolean[sum + 1][len + 1];
          dp[0][0] = true;
          for(int i = 1; i <= sum; i++){
              for(int j = 1; j <= len; j++){
                  dp[i][j] = dp[i][j - 1];
                  dp[i][j] |= i - nums[j - 1] >= 0 ? dp[i - nums[j - 1]][j - 1]: false;
              }
          }
          return dp[sum][len];
      }
  }

Reference

  1. [Algorithm 01 knapsack question DP](https://seanforfun.github.io/algorithm/2018/03/07/01KnapSack.html)