Bitset Subset Sum 59cda75d

Subset-sum reachability via bitset shifts: which totals in [0, cap] are achievable using a subset of a[]. Each item processed in O(cap / 64) instead of O(cap) — the same shift trick generalizes to 2D reachability (track a bitset per value of a second resource, shift each one) when there are two constrained sums, as in the classic "knapsack with two capacities" variant.

Time: O(n \cdot cap / 64). tested

content/dp/bitset-subset-sum.h

template <size_t CAP>
bitset<CAP> subsetSumReachable(vector<int> &a) {
    bitset<CAP> reachable;
    reachable[0] = 1;
    for (int x : a) reachable |= reachable << x;
    return reachable;
}