1248. Every Subset, as a Number
Given n integers and a target t, print how many subsets sum to exactly
t. The empty subset counts and sums to zero.
With n at most 20 there are at most about a million subsets, which is few
enough to examine every one. The trick is that a subset IS an integer: bit k
of the number says whether element k is in the subset, so counting from 0 to
2^n - 1 enumerates every subset exactly once with no recursion.
That correspondence is why a bound of 20 in a problem statement is close to being told to use a mask.
Constraints - `1 ≤ n ≤ 20` - `-1000000000 ≤ t ≤ 1000000000` - `-100000 ≤ a[i] ≤ 100000`
Input
The first line contains two integers n and t.
The second line contains n space-separated integers.
Output
Print one integer: how many subsets sum to exactly t.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.