LeetCode416. Partition Equal Subset Sum（动态规划）

LeetCode416. Partition Equal Subset Sum（动态规划）

• Medium
• Accepted：79,322
• Submissions：197,654

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.

链接

https://leetcode.com/problems/partition-equal-subset-sum

题意

给定一个只包含正整数的非空数组，判断这个数组是否可以划分为两个子集，使得这个两个子集的元素和相等。

题解

两个子集的元素和相等，实际上就是在数组中找到一些元素使得它们的和为sum/2（sum为数组元素和）。然后就可以通过类似01背包的思路解决这道问题，我们只需要考虑“重量”而无需考虑“价值”。

假设$F(n, sum)​$表示能否在n个元素中寻找某些元素使得和为sum，那么：$F(n, sum) = F(n-1, sum) || F(n-1, sum -nums[i])​$

考虑自顶向下的记忆化搜索递归和自底向上的动态规划，时间复杂度$O(n*sum)$。优化之后的空间复杂度为$O(sum)$。

代码

• 递归

class Solution {
private:
    vector <vector<int> > memo;
    bool solve(vector<int>& nums, int index, int C)
    {
        if (C == 0)
            return true;
        if (C < 0 || index < 0)
            return false;
        if (memo[index][C] != -1)
            return memo[index][C];
        memo[index][C] = solve(nums, index - 1, C) || solve(nums, index - 1, C - nums[index]);
        return memo[index][C];
    }
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size(), sum = 0;
        for (int i = 0; i < n; ++i)
            sum += nums[i];
        if (n == 0 || sum % 2 == 1)
            return false;
        int C = sum / 2;
        memo = vector <vector <int>> (n, vector<int>(C + 1, -1));
        return solve(nums, n - 1, C);
    }
};

• 动态规划

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 (n == 0 || sum % 2 == 1)
            return false;
        int C = sum / 2;
        vector <bool> dp(C + 1, false);
        for (int i = 0; i <= C; ++i)
            dp[i] = (nums[0] == i);
        for (int i = 1; i < n; ++i)
            for (int j = C; j >= nums[i]; --j)
                dp[j] = (dp[j] || dp[j - nums[i]]);
        return dp[C];
    }
};

The end.
2019年4月5日 星期五