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}).