[Leetcode] #416 Partition Equal Subset Sum

Discription:

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:

01背包问题。

bool canPartition(vector<int>& nums) { int sum = 0; int n = nums.size(); for (int i = 0; i < nums.size(); i++){ sum += nums[i]; } if (sum % 2 == 1) return false; sum = sum / 2; vector<vector<int>> dp(n + 1, vector<int>(sum + 1, 0)); for (int i = 1; i <= n; i++){ for (int j = 1; j <= sum; j++){ if (j >= nums[i - 1]){ dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]); } else{ dp[i][j] = dp[i - 1][j]; } } } return dp[n][sum] == sum ? true : false; } bool canPartition(vector<int>& nums) { //利用滚动数组实现 int sum = 0; int n = nums.size(); for (int i = 0; i < nums.size(); i++){ sum += nums[i]; } if (sum % 2 == 1) return false; sum = sum / 2; vector<int> dp(sum + 1, 0); for (int i = 1; i <= n; i++){ for (int j = sum; j >= nums[i-1]; j--) dp[j] = max(dp[j], dp[j - nums[i - 1]] + nums[i - 1]); } return dp[sum] == sum ? true : false; }GitHub-Leetcode: https://github.com/wenwu313/LeetCode