Given an array of integers and a target sum , determine if any subset of the array sums to exactly . For example, with array and target , the answer is yes because and both sum to . Constraints: . With this small, 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?