subset_sum_partition.cpp

// subset_sum_partition.cpp
// -----------------------------------------------------------------
// Subset Sum 與 Partition：
//   1. Subset Sum 偽多項式 DP O(n·T) + 還原子集
//   2. Meet-in-the-Middle O(2^(n/2))（值域大時的武器）
//   3. Partition（總和均分）= Subset Sum 特例
//   4. 最平衡分割：最小化兩組差
//
// Compile: g++ -std=c++17 -O2 -Wall -Wextra -o subset_sum_partition subset_sum_partition.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <random>
#include <chrono>

using namespace std;

// ---------- 1. DP + 還原 ----------
// from[s] = 使 s 第一次可達的「物品索引」，-1 表示不可達（s=0 例外）
pair<bool, vector<int>> subsetSumDP(const vector<int>& a, int target) {
    vector<int> from(target + 1, -2);          // -2 = 不可達
    from[0] = -1;                              // -1 = 起點
    for (int i = 0; i < (int)a.size(); ++i)
        for (int s = target; s >= a[i]; --s)
            if (from[s] == -2 && from[s - a[i]] != -2)
                from[s] = i;
    if (from[target] == -2) return {false, {}};
    vector<int> chosen;                        // 還原
    int s = target;
    while (s > 0) {
        int i = from[s];
        chosen.push_back(i);
        s -= a[i];
    }
    reverse(chosen.begin(), chosen.end());
    return {true, chosen};
}

// ---------- 2. Meet-in-the-Middle ----------
bool subsetSumMITM(const vector<int>& a, long long target) {
    int n = (int)a.size(), h = n / 2;
    auto sums = [](const vector<int>& part) {
        int m = (int)part.size();
        vector<long long> out;
        out.reserve(1LL << m);
        for (int mask = 0; mask < (1 << m); ++mask) {
            long long s = 0;
            for (int i = 0; i < m; ++i)
                if (mask & (1 << i)) s += part[i];
            out.push_back(s);
        }
        return out;
    };
    vector<int> L(a.begin(), a.begin() + h), R(a.begin() + h, a.end());
    auto sl = sums(L), sr = sums(R);
    sort(sr.begin(), sr.end());
    for (long long s : sl)
        if (binary_search(sr.begin(), sr.end(), target - s)) return true;
    return false;
}

// ---------- 3. Partition：總和為偶數且一半可達 ----------
pair<bool, vector<int>> partitionEqual(const vector<int>& a) {
    int total = accumulate(a.begin(), a.end(), 0);
    if (total % 2 != 0) return {false, {}};
    return subsetSumDP(a, total / 2);
}

// ---------- 4. 最平衡分割：找 <= total/2 的最大可達和 ----------
int minPartitionDiff(const vector<int>& a) {
    int total = accumulate(a.begin(), a.end(), 0);
    int half = total / 2;
    vector<bool> dp(half + 1, false);
    dp[0] = true;
    for (int x : a)
        for (int s = half; s >= x; --s)
            if (dp[s - x]) dp[s] = true;
    for (int s = half; s >= 0; --s)
        if (dp[s]) return total - 2 * s;       // 兩組差 = total - 2s
    return total;
}

static void printSet(const vector<int>& a, const vector<int>& idx) {
    int sum = 0;
    cout << "{";
    for (size_t k = 0; k < idx.size(); ++k) {
        cout << a[idx[k]] << (k + 1 < idx.size() ? "," : "");
        sum += a[idx[k]];
    }
    cout << "} (sum=" << sum << ")";
}

int main() {
    // ---- 範例 1：Subset Sum 基本 + 還原 ----
    cout << "=== Example 1: subset sum with reconstruction ===\n";
    vector<int> a = {3, 34, 4, 12, 5, 2};
    for (int t : {9, 11, 30}) {
        auto [ok, idx] = subsetSumDP(a, t);
        cout << "target=" << t << " -> " << (ok ? "YES  " : "no");
        if (ok) printSet(a, idx);
        cout << "\n";
    }
    cout << "\n";

    // ---- 範例 2：Partition ----
    cout << "=== Example 2: partition into two equal halves ===\n";
    vector<int> b = {1, 5, 11, 5};
    auto [okB, idxB] = partitionEqual(b);
    cout << "{1,5,11,5}: " << (okB ? "YES  side A = " : "no");
    if (okB) printSet(b, idxB);
    cout << "\n";
    vector<int> c = {1, 2, 3, 5};
    cout << "{1,2,3,5}: " << (partitionEqual(c).first ? "YES" : "no (odd total or unreachable)") << "\n\n";

    // ---- 範例 3：最平衡分割 ----
    cout << "=== Example 3: most balanced split (min difference) ===\n";
    vector<int> d = {8, 6, 5, 14, 13, 9, 12, 7};
    cout << "{8,6,5,14,13,9,12,7} total=" << accumulate(d.begin(), d.end(), 0)
         << " -> min diff = " << minPartitionDiff(d) << "\n";
    vector<int> e = {3, 1, 4, 2, 2, 1};
    cout << "{3,1,4,2,2,1} total=13 -> min diff = "
         << minPartitionDiff(e) << " (odd total, best split is 6/7)\n\n";

    // ---- 範例 4：值域大時 DP 失效，MITM 接手 ----
    cout << "=== Example 4: huge values -> meet-in-the-middle ===\n";
    mt19937 rng(7);
    uniform_int_distribution<long long> big(1e12, 9e12);
    vector<int> f36;
    vector<long long> raw;
    for (int i = 0; i < 36; ++i) raw.push_back(big(rng));
    // 挑其中 7 個當作可達目標
    long long target = raw[2] + raw[5] + raw[11] + raw[17] + raw[23] + raw[29] + raw[33];
    // MITM 直接吃 long long；DP 需要陣列大小 = target，根本開不出來
    vector<int> dummy;   // (DP 版此處不適用，只示範 MITM)
    auto t0 = chrono::steady_clock::now();
    // 轉存到 int 會溢位，MITM 這裡用 long long 版本
    {
        // 重寫一份 long long 輸入的 MITM（沿用同邏輯）
        int n = (int)raw.size(), h = n / 2;
        auto sums = [](const vector<long long>& part) {
            int m = (int)part.size();
            vector<long long> out;
            out.reserve(1LL << m);
            for (int mask = 0; mask < (1 << m); ++mask) {
                long long s = 0;
                for (int i = 0; i < m; ++i)
                    if (mask & (1 << i)) s += part[i];
                out.push_back(s);
            }
            return out;
        };
        vector<long long> L(raw.begin(), raw.begin() + h),
                          R(raw.begin() + h, raw.end());
        auto sl = sums(L), sr = sums(R);
        sort(sr.begin(), sr.end());
        bool found = false;
        for (long long s : sl)
            if (binary_search(sr.begin(), sr.end(), target - s)) { found = true; break; }
        auto t1 = chrono::steady_clock::now();
        cout << "n=36, values ~1e12, target reachable? "
             << (found ? "YES" : "no") << "  ("
             << chrono::duration<double, milli>(t1 - t0).count() << " ms, "
             << "2^18 = 262144 sums per half)\n";
        cout << "(DP would need an array of ~" << target
             << " entries -> impossible; MITM wins)\n";
    }
    (void)f36; (void)dummy; (void)subsetSumMITM;
    return 0;
}