416. Partition Equal Subset Sum

Medium (Trung bình) C++ 🔗 Xem trên LeetCode

📋 Đề Bài

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

🧠 Thuật Toán & Kỹ Thuật

Dynamic Programming (Quy hoạch động)Bit Manipulation (Thao tác bit)
⏱️ Thời gian O(n×m)
💾 Không gian O(n×m)

💻 Lời Giải

C++ 0416-partition-equal-subset-sum.cpp 
class Solution {
public:
    vector<vector<int>> dp;
    int n;
    bool rec(vector<int> &nums, int s, int i = 0) {
        if (s < 0 || i >= n) {
            return false;
        }
        if (dp[s][i] != -1) {
            return dp[s][i];
        }
        if (s == 0) {
            return true;
        }
        return dp[s][i] = rec(nums, s - nums[i], i + 1) | rec(nums, s, i + 1);
    }
    bool canPartition(vector<int>& nums) {
        int s = 0;
        n = nums.size();
        for (int i = 0; i < n; ++i) {
            s += nums[i];
        }
        if (s & 1) {
            return false;
        }
        s /= 2;
        sort(nums.begin(), nums.end());
        dp.resize(s + 1, vector<int>(n, -1));
        return rec(nums, s);
    }
};