[LeetCode] 416. Partition Equal Subset Sum

[frdmu]

Given a non-empty array nums 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.

 

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

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

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

 

解法：
动态规划。0-1背包。代码如下：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size(), sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) return false;

        vector<vector<bool>> dp(n+1, vector<bool>(sum/2+1, false));
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        } 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum/2; j++) {
                if (j - nums[i-1] >= 0) {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        return dp[n][sum/2];
    }
};

/*
    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
    0 <= i <= n, 0 <= j <= W
    base case:
    dp[0][...] = false, dp[...][0] = true   
*/

Refer:
经典动态规划：子集背包问题