Partition Equal Subset Sum trong C++

Cho mảng số dương không rỗng. Kiểm tra có thể chia thành 2 subset có tổng bằng nhau hay không.

Ví dụ: [1,5,11,5] → true, vì chia được [1,5,5] và [11].

Giải thuật (DP Subset Sum)

• Tính tổng sum. Nếu lẻ → false.
• target = sum/2.
• Mảng dp[target+1], dp[0]=true.
• Duyệt từng số x trong mảng:
  • Duyệt j = target .. x giảm: dp[j] = dp[j] || dp[j-x].
• Trả về dp[target].

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

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

int main() {
    Solution ob;
    vector<int> v = {1,5,11,5};
    cout << ob.canPartition(v);
    return 0;
}

Input

[1,5,11,5]

Output

1