Practice - Subset Sum Count

Practice problem: given an array of positive integers and a target sum $S$, count how many subsets sum exactly to $S$. This is the counting version of Partition.

Let $dp[s]$ = number of subsets summing to $s$. Base case: $dp[0] = 1$ (empty subset). Transition: for each element $x$, update $dp[s] = dp[s] + dp[s-x]$ for $s$ from target down to $x$. Try it on $[1, 2, 3, 4, 5]$ with target $5$. Expected answer: $3$ subsets ($\{5\}$, $\{1,4\}$, $\{2,3\}$).