Partition to K Equal Sum Subsets ใน C++

โจทย์: Partition to K Equal Sum Subsets

ให้อาร์เรย์จำนวนเต็ม nums และจำนวนเต็มบวก k ตรวจสอบว่าสามารถแบ่งอาร์เรย์ออกเป็น k ส่วนย่อย (subsets) ที่ไม่ว่างเปล่า ได้หรือไม่ โดยที่ ผลรวมของแต่ละส่วนเท่ากันทุกส่วน

ตัวอย่าง: nums = [4,3,2,3,5,2,1], k = 4

สามารถแบ่งได้: [5], [1,4], [2,3], [2,3] ผลรวมแต่ละชุด = 5 → True

อัลกอริทึม: DP with Bitmask (Dynamic Programming on Subsets)

เนื่องจาก n ≤ 16 (ในปัญหา LeetCode ทั่วไป) สามารถใช้ bitmask แทน subset ได้ (2^n สถานะ)

1. คำนวณ total_sum = sum(nums) หาก total_sum % k != 0 → false
2. target = total_sum / k (ผลรวมเป้าหมายของแต่ละ subset)
3. หากมีองค์ประกอบใด > target → false
4. เรียง nums จากมากไปน้อย (pruning เร็วขึ้น)
5. DP state: dp[mask] = true หาก subset ที่แทนโดย mask สามารถแบ่งเป็นกลุ่มที่สมบูรณ์ได้ (บางกลุ่มอาจยังไม่เต็ม)
6. total[mask] = ผลรวมของ subset ปัจจุบันที่ยังไม่เต็ม (mod target)
7. เริ่ม dp[0] = true, total[0] = 0
8. วนทุก mask จาก 0 ถึง 2^n - 1:
   • ถ้า dp[mask] เป็น true:
     • ลองเพิ่มแต่ละองค์ประกอบ j ที่ยังไม่อยู่ใน mask
     • new_mask = mask | (1 << j)
     • ถ้า nums[j] <= target - total[mask] (ใส่ได้ใน subset ปัจจุบัน):
       • dp[new_mask] = true
       • total[new_mask] = total[mask] + nums[j]
     • มิฉะนั้น break (เพราะ nums เรียงจากมากไปน้อย ตัวหลังจะใหญ่กว่า ใส่ไม่ได้แน่)
9. ส่งคืน dp[(1<<n)-1]

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

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

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int n = nums.size();
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k != 0) return false;
        int target = sum / k;
        
        sort(nums.begin(), nums.end(), greater<int>()); // เรียงมากไปน้อย
        if (nums[0] > target) return false;
        
        vector<bool> dp(1 << n, false);
        vector<int> total(1 << n, 0);
        dp[0] = true;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (!dp[mask]) continue;
            for (int j = 0; j < n; j++) {
                if (mask & (1 << j)) continue; // ใช้แล้ว
                int new_mask = mask | (1 << j);
                if (new_mask == mask) continue;
                
                int curr_sum = total[mask];
                if (nums[j] <= target - curr_sum) {
                    dp[new_mask] = true;
                    total[new_mask] = curr_sum + nums[j];
                } else {
                    break; // nums เรียงมากไปน้อย ตัวต่อไปจะใหญ่กว่า ใส่ไม่ได้แน่
                }
            }
        }
        return dp[(1 << n) - 1];
    }
};

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

Input

[4,3,2,3,5,2,1] 4

Output

true

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

• เวลา: O(n × 2^n) - n ≤ 16 ทำได้ในเวลาอันเหมาะสม
• พื้นที่: O(2^n)

วิธีแก้อื่น: Backtracking/DFS กับ pruning (เรียงมากไปน้อย, skip duplicates) ซึ่งในทางปฏิบัติมักเร็วกว่า DP bitmask สำหรับ n ใหญ่