416.Partition-Equal-Subset-Sum

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];
}