Subset Sum and Partition

Subset sum. Given $a_1,\dots ,a_n$ and a target $S$, is there a subset summing to exactly $S$?
Partition. Split the multiset into two parts with equal sums (subset sum with $S=\mathrm{total}/2$).

Both are NP-complete — but only weakly, so a pseudo-polynomial DP exists.

The DP — $O(nS)$

bool subsetSum(const vector<int>& a, int S) {
    vector<bool> dp(S + 1, false);
    dp[0] = true;
    for (int x : a)
        for (int s = S; s >= x; s--)                 // DOWNWARD: each item once
            dp[s] = dp[s] || dp[s - x];
    return dp[S];
}

The downward loop is what makes each item usable once — see Knapsack.

With a bitset — $O(nS/64)$

bitset<MAXS + 1> dp;
dp[0] = 1;
for (int x : a) dp |= dp << x;
bool ok = dp[S];

A 64× speedup, turning $nS=10^{10}$ into $1.5\cdot 10^8$. This is the single most valuable optimisation for this problem family, and it should be the default whenever $S$ is known and the answer is boolean. See Bitset Optimization.

Huge values — meet in the middle

When $S$ is astronomical but $n\le 40$:

// enumerate 2^(n/2) sums from each half; sort one, binary search the other
sort(B.begin(), B.end());
for (long long x : A) if (binary_search(B.begin(), B.end(), S - x)) return true;

$O(2^{n/2}\cdot n)$ time and $O(2^{n/2})$ memory. Handles $n=40$-$44$.

Schroeppel-Shamir achieves $O(2^{n/2})$ time with only $O(2^{n/4})$ memory by splitting into four parts.

The decision table

Situation	Method	Cost
$\sum a_i\le 10^5$	DP	$O(nS)$
$\sum a_i\le 10^6$, boolean	bitset DP	$O(nS/64)$
$n\le 40$, huge values	meet in the middle	$O(2^{n/2})$
$n\le 50$, minimise the difference	complete Karmarkar-Karp
Approximate, large $n$	KK differencing	$O(n\log n)$
Few distinct values	DP over counts, or bounded knapsack
Count the subsets	the same DP with += instead of |	$O(nS)$
$k$-way equal partition	bitmask DP or backtracking	$O(2^{n}n)$

The distinct-values bound

If the $a_i$ are distinct positive integers summing to $W$, then $n=O(\sqrt{W})$ — because $1+2+\cdots +n\le W$. So “distinct weights with a bounded total” is secretly a small-$n$ problem, and a bounded-knapsack DP over the distinct values is efficient. This observation converts several intimidating constraints into easy ones.

Minimum-difference partition

// reachable sums up to total/2; take the largest
for (int s = total / 2; s >= 0; s--)
    if (dp[s]) return total - 2 * s;

With a bitset: for (int s = total/2; s >= 0; s--) if (dp[s]) ..., or use _Find_next from the appropriate end.

Reconstruction

The boolean DP loses the which subset information. To recover it:

• keep the full 2D table dp[i][s] and walk backwards, or
• store, for each reachable sum, the last item that produced it (a from[s] array), which needs $O(S)$ extra memory and works with the 1D DP.

vector<int> from(S + 1, -1);
for (int i = 0; i < n; i++)
    for (int s = S; s >= a[i]; s--)
        if (!dp[s] && dp[s - a[i]]) { dp[s] = true; from[s] = i; }
// then walk back from S

Related problems

Problem	Relation
0/1 knapsack	subset sum with values
Coin change	unbounded version
Makespan / multiway partition	$k$-way generalisation
Bin packing	related, also NP-hard
Equal-sum subsets of a given size	add a count dimension
Sum divisible by $k$	DP over residues, $O(nk)$ — polynomial
Subset XOR	linear basis, $O(n\log C)$ — polynomial

The last two rows are worth noting: replacing “sum equals $S$” with “sum divisible by $k$” or “XOR equals $S$” makes the problem polynomial. Read the statement carefully — those variants look identical and are far easier.

See also: Knapsack · Meet in the Middle · Bitset Optimization