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:

1
2
3
4
5
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

1
2
3
4
5
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

思路

这是一个典型的背包问题。背包问题涉及到了二维的动态规划。这也是我第一次利用二维DP的方法来解决LeetCode当中的问题。

在这道题目中，我们所期待的结果是可以把一个数组分成两半，且两部分的数组值相同。因此我们可以构建一个二维数组，纵轴是数组的元素个数，横轴是所期待的数组值之和（在这里就是数组所有元素和的一半）。在这里，所期待数组值之和就是”背包的重量“，我们需要从纵轴的所有元素挑选几个，从而使得背包的重量恰好为期待的值。这样就可以转化为背包问题了。

但是有更好的方法，可以把空间复杂度降低到一个维度，没想明白。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        if (sum % 2 != 0){
            return false;
        }
        else{
            int[][] dp = new int[nums.length+1][sum/2+1];
            for (int i = 1; i < sum/2+1; i++){
                int cur = 0;
                for(int j = 1; j < nums.length; j++){
                    if (nums[j] <= i){
                        int prev = dp[j-1][i-nums[j]] + nums[j];
                        dp[j][i] = Math.max(cur, prev);
                        cur = Math.max(dp[j][i], cur);
                    }
                }
            }
            if(dp[nums.length-1][sum/2] == sum/2){
                return true;
            }
            else{
                return false;
            }
        }
    }
}

参考资料：

http://blog.csdn.net/mu399/article/details/7722810

https://discuss.leetcode.com/topic/62312/java-solution-similar-to-backpack-problem-easy-to-understand