ACDream 1726 A Math Game：部分和問題 DFS + 前綴和剪枝

題目大意

給定 n ≤ 40 個整數和目標值 H，判斷能否選取若干數使其和恰好等於 H。多測試用例。

算法選擇：DFS + 剪枝 (Meet-in-the-Middle 亦可)

n ≤ 40，2⁴⁰ 過大。但數據可能較弱，DFS 配合強剪枝可通過。標準解法為 Meet-in-the-Middle：分成兩半各枚舉子集和 (2²⁰ ≈ 10⁶)，排序雙指針查找，O(2^{n/2})。本文講解 DFS 剪枝版。

剪枝策略

1. 排序：將數組按絕對值或原值排序 (視正負情況)
2. 前綴和 / 後綴和：預計算 sum[i] = a[i] + ... + a[n] (剩餘最大可能和)
3. 剪枝條件：
   • 當前和 > H → 剪枝 (若全非負)
   • 當前和 + 剩餘總和 < H → 剪枝 (即使全選也不夠)
   • 已找到解 → 全局標記返回

完整代碼

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

using ll = long long;
const int MAXN = 45;
ll a[MAXN], suffixSum[MAXN];
ll H;
int n;
bool found;

void dfs(int idx, ll curSum) {
    if (found) return;
    if (curSum == H) { found = true; return; }
    if (idx > n) return;
    // 剪枝：即使選完剩餘也不夠 / 已經超過 (假設非負)
    if (curSum + suffixSum[idx] < H) return;
    if (curSum > H) return; // 若有負數需移除此剪枝

    dfs(idx + 1, curSum + a[idx]); // 選
    dfs(idx + 1, curSum);          // 不選
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while (cin >> n >> H) {
        for (int i = 1; i <= n; ++i) cin >> a[i];
        // 可選：排序優化剪枝效果
        // sort(a+1, a+n+1, [](ll x, ll y){ return abs(x) > abs(y); });

        suffixSum[n+1] = 0;
        for (int i = n; i >= 1; --i) suffixSum[i] = suffixSum[i+1] + a[i];

        found = false;
        dfs(1, 0);
        cout << (found ? "Yes" : "No") << '\n';
    }
    return 0;
}

Meet-in-the-Middle 標準解法 (推薦)

bool meetInMiddle(vector& a, ll H) {
    int n = a.size();
    int mid = n / 2;
    vector left, right;

    // 枚舉左半所有子集和
    for (int mask = 0; mask < (1<>i & 1) sum += a[i];
        left.push_back(sum);
    }
    // 枚舉右半
    for (int mask = 0; mask < (1<<(n-mid)); ++mask) {
        ll sum = 0;
        for (int i = 0; i < n-mid; ++i) if (mask>>i & 1) sum += a[mid+i];
        right.push_back(sum);
    }

    sort(right.begin(), right.end());
    for (ll x : left) {
        if (binary_search(right.begin(), right.end(), H - x)) return true;
    }
    return false;
}

複雜度對比

總結

部分和問題 (Subset Sum) 是經典 NP-Complete 問題。n ≤ 40 時，Meet-in-the-Middle 是理論最優、工程最穩健的解法。DFS 剪枝雖代碼短，但依賴數據分布，比賽中建議實現 Meet-in-the-Middle 確保 AC。本題 ACDream 1726 數據較弱，DFS 4ms 通過，但不具備普適性。