152. Subset Sum Problem

Given an array of n non-negative integers and a target sum, print 'Yes' if some subset of the array's elements (possibly empty, possibly all of it) adds up to exactly the target, otherwise print 'No'.

Input: The first line contains an integer n. The second line contains n space-separated non-negative integers. The third line contains the integer target. Output: Print 'Yes' if some subset sums exactly to the target, otherwise print 'No'.

1 <= n <= 1000, 0 <= target <= 10^5

This problem's specific constraints (larger n, bounded target) are exactly what signal that a DP approach is expected over pure backtracking - a smaller n with an unbounded target would instead favor the backtracking/enumeration approach.

Check whether any subset of an array's elements adds up to exactly a given target. Brute force: Try every one of the 2^n possible subsets directly and check each one's sum - this works but can be slow for large n if done naively without pruning, especially given the larger constraint here (n up to 1000, though target is capped at 10^5 which enables the DP approach instead). Optimised: A DP table dp[i][s] = 'can the first i elements form sum s' avoids the exponential subset enumeration entirely - since the target itself is bounded (up to 10^5), a table indexed by element-count and achievable-sum reduces the problem to O(n * target), far better than 2^n for large n.

Recursively decide, for each element in turn, whether to include it in the subset or skip it, and check whether any resulting combination sums exactly to the target. This is correct because it explores every possible subset exactly once, but the number of subsets doubles with every additional element, so the recursion tree grows exponentially and becomes infeasible for larger arrays. Time: O(2^n) Space: O(n)

Maintain a single boolean array dp of size target+1 where dp[0] starts true (the empty subset always sums to zero), and for each array element, update dp from the highest index down to the element's value, setting dp[s] to true whenever dp[s - element] is already true. This is correct because processing sums in decreasing order guarantees each element is only ever used once per element-processing pass, matching the subset semantics, and it removes the need for the per-index dimension of the memo table by reusing the same array across all n elements. Time: O(n * target) Space: O(target)

Use the same include/exclude recursion as the brute force, but memoize results keyed by (current index, remaining target) so that once a particular (index, remaining sum) combination has been resolved as achievable or not, it is never recomputed. This is correct because the recursion only ever depends on these two parameters, so caching eliminates the exponential re-exploration of identical subproblems, collapsing the work down to one computation per distinct (index, sum) pair. Time: O(n * target) Space: O(n * target)

1. Recurse on each element: try INCLUDING it (reducing the remaining target by its value) or EXCLUDING it. 2. Prune eagerly: stop exploring any branch where the running sum already exceeds the target. 3. If any branch reaches exactly 0 remaining target, answer Yes.

Time: O(n * target) with the DP table approach - a polynomial-time solution, in contrast to the O(2^n) pure backtracking approach which would be too slow for n up to 1000. Space: O(n * target) for the full DP table (reducible to O(target) with a rolling 1D array, since each row only depends on the row before it).

Test target = 0 (empty subset always works, 'Yes'), n = 1, and n = 1000 with target = 10^5 for performance.

Be ready to explain WHY the DP approach here isn't 'true' polynomial time in the strict sense (it's pseudo-polynomial, since its complexity depends on the target's VALUE, not just the input's size) - a subtlety often specifically probed in interviews.