Partition Problem (แบ่งเซตให้ผลรวมเท่ากัน)

กำหนดเซตของจำนวนเต็ม ต้องการทราบว่าสามารถแบ่งเป็น 2 subset ที่มี ผลรวมเท่ากัน ได้หรือไม่

ตัวอย่าง Input และ Output

Input: {3, 1, 1, 2, 2, 1}
Sum = 10 (คู่)
Output: True
Partitions: {3, 1, 1} และ {2, 2, 1} (ทั้งคู่รวม = 5)

อัลกอริทึม Dynamic Programming (Subset Sum)

ฟังก์ชัน checkPartition(set, n)

ขั้นตอน:

1. คำนวณ sum ของทุกสมาชิก
2. ถ้า sum เป็นคี่ → คืน false (แบ่งไม่ได้)
3. Target = sum/2 → ต้องหา subset ที่รวมได้ target
4. สร้างตาราง partTab[target+1][n+1] (boolean)
5. Base Cases:
   • Row 0 (target=0): ทุกค่า = true (empty subset)
   • Col 0 (0 items): ทุกค่า = false (ยกเว้น [0][0])
6. for i = 1 ถึง target:
   • for j = 1 ถึง n:
     • partTab[i][j] = partTab[i][j-1] (ไม่เอา item j)
     • ถ้า i >= set[j-1] → partTab[i][j] = partTab[i][j] || partTab[i-set[j-1]][j-1] (เอา item j)
7. คืน partTab[target][n]

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

#include <iostream>
#include <vector>
using namespace std;

bool checkPartition(int set[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) sum += set[i];
    if (sum % 2 != 0) return false;

    int target = sum / 2;
    vector> partTab(target+1, vector(n+1, false));

    // Base cases
    for (int i = 0; i <= n; i++) partTab[0][i] = true;
    for (int i = 1; i <= target; i++) partTab[i][0] = false;

    // Fill table
    for (int i = 1; i <= target; i++) {
        for (int j = 1; j <= n; j++) {
            partTab[i][j] = partTab[i][j-1];
            if (i >= set[j-1])
                partTab[i][j] = partTab[i][j] || partTab[i - set[j-1]][j-1];
        }
    }
    return partTab[target][n];
}

int main() {
    int set[] = {3, 1, 1, 2, 2, 1};
    int n = 6;
    if (checkPartition(set, n))
        cout << "Given Set can be divided into two subsets of equal sum.";
    else
        cout << "Given Set can not be divided into two subsets of equal sum.";
    return 0;
}

Output

Given Set can be divided into two subsets of equal sum.

ความซับซ้อน

• Time: O(n × target)
• Space: O(n × target) (ลดเป็น O(target) ได้)

หมายเหตุ

นี่คือกรณีพิเศษของ Subset Sum Problem (NP-Complete) แต่ถ้า target ไมใหญ่ DP นี้ทำได้ (Pseudo-polynomial time)