Given an array of n integers and a target sum S, determine if any subset of the array sums to exactly S. For example, with array [3,1,4,2] and target 5, the answer is yes because {3,2} and {1,4} both sum to 5. Constraints: n≤20. With n this small, 2n≈1 million subsets is feasible to enumerate.
This is the simplest bitmask problem: iterate all subsets, check their sums. Before reading on, try to write the brute-force solution. How would you represent each subset? How would you compute its sum?