Partition Equal Subset Sum ใน C++

ตัวอย่าง: nums = [1, 5, 11, 5]

ผลรวมรวม = 22, เป้าหมายแต่ละส่วน = 11

สามารถแบ่งได้: [1, 5, 5] และ [11] → true

อัลกอริทึม: 0/1 Knapsack (Subset Sum) DP

หากผลรวมรวมเป็นคี่ → ไม่สามารถแบ่งครึ่งได้ → false

เป้าหมาย: หา subset ที่ผลรวม = target = sum / 2

กำหนด dp[i] = true หากสามารถทำผลรวม i ได้จาก subset ของ nums

Initialization:

dp[0] = true (ผลรวม 0 ทำได้ตลอด: เลือกชุดว่าง)

Transition (0/1 Knapsack - วนย้อนกลับ):

สำหรับแต่ละ num ใน nums:

for (int i = target; i >= num; i--)
    dp[i] = dp[i] || dp[i - num];

สำคัญ: ต้องวน i จาก target ลงมา num (ย้อนกลับ) เพื่อไม่ให้ใช้ num เดียวกันหลายครั้ง (0/1 knapsack) หากวนจากน้อยไปมาก จะกลายเป็น unbounded knapsack (ใช้ซ้ำได้)

ตัวอย่างโค้ด C++

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

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum & 1) return false; // ผลรวมคี่
        
        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        
        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[target];
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 5, 11, 5};
    cout << (ob.canPartition(v) ? "true" : "false") << endl;
    return 0;
}

Input

[1,5,11,5]

Output

true

ความซับซ้อน (Complexity)

• เวลา: O(n × target) โดย target = sum/2
• พื้นที่: O(target)

ข้อจำกัด: ใช้ได้ก็ต่อเมื่อ target ไม่ใหญ่เกินไป (sum ≤ ~20000) หาก sum ใหญ่มาก ต้องใช้ Meet-in-the-Middle หรือ Approximation

แก้ไขจากโค้ดต้นฉบับ: โค้ดต้นฉบับมี for(int j =sum;j-x>=0;j--) ซึ่ง j-x >= 0 เทียบเท่า j >= x เขียนให้ชัดเจนขึ้น และใช้ accumulate แทนลูปรวมเอง