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.

解：
1.nums和一定是被2整除。
2.定義一個一維的dp數(shù)組瞻离，其中dp[i]表示數(shù)字i是否是原數(shù)組的任意個子集合之和秉溉，那么我們我們最后只需要返回dp[target]就行了。我們初始化dp[0]為true饮潦，由于題目中限制了所有數(shù)字為正數(shù)燃异，那么我們就不用擔(dān)心會出現(xiàn)和為0或者負(fù)數(shù)的情況。
3.關(guān)鍵問題就是要找出狀態(tài)轉(zhuǎn)移方程了继蜡，我們需要遍歷原數(shù)組中的數(shù)字回俐，對于遍歷到的每個數(shù)字nums[i]，我們需要更新dp數(shù)組稀并，要更新[nums[i], target]之間的值仅颇，那么對于這個區(qū)間中的任意一個數(shù)字j，如果dp[j - nums[i]]為true的話碘举，那么dp[j]就一定為true忘瓦，于是狀態(tài)轉(zhuǎn)移方程如下：

dp[j] = dp[j] || dp[j - nums[i]] (nums[i] <= j <= target)

public boolean canPartition(int[] nums) {
    int sum = 0;
    
    for (int num : nums) {
        sum += num;
    }
    
    if ((sum & 1) == 1) {
        return false;
    }
    sum /= 2;

    int n = nums.length;
    boolean[][] dp = new boolean[n+1][sum+1];
    for (int i = 0; i < dp.length; i++) {
        Arrays.fill(dp[i], false);
    }
    
    dp[0][0] = true;
    
    for (int i = 1; i < n+1; i++) {
        dp[i][0] = true;
    }
    for (int j = 1; j < sum+1; j++) {
        dp[0][j] = false;
    }
    
    for (int i = 1; i < n+1; i++) {
        for (int j = 1; j < sum+1; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= nums[i-1]) {
                dp[i][j] = (dp[i][j] || dp[i-1][j-nums[i-1]]);
            }
        }
    }
   
    return dp[n][sum];
}

優(yōu)化方法：

public boolean canPartition(int[] nums) {
    int sum = 0;
    
    for (int num : nums) {
        sum += num;
    }
    
    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];
}