[数据结构与算法]LeetCode-416. Partition Equal Subset Sum [C++][Java]

LeetCode-416. Partition Equal Subset SumLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.https://leetcode.com/problems/partition-equal-subset-sum/

题目描述

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背包问题。

【C++】

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0, n = nums.size();
        for (int num : nums) {sum += num;}
        if (sum % 2 == 1) {return false;}
        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        for (int num : nums) {
            for (int j = target; j >= num; --j) {
                dp[j] = dp[j] || dp[j-num];
            }
        }
        return dp[target];
    }
};

【Java】

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0, n = nums.length;
        for (int num : nums) {sum += num;}
        if (sum % 2 == 1) {return false;}
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int j = target; j >= num; --j) {
                dp[j] = dp[j] || dp[j-num];
            }
        }
        return dp[target];
    }
}