Exact Grant Subset Plans
Preview mode. Log in to edit, run, submit, and save progress.
Exact Grant Subset Plans
A grant engine receives package sizes and a requested target amount. Each package can be selected at most once. A plan is valid if the sum of selected package sizes is exactly target. The order of selection does not matter; only the subset of package indices matters. Because the number of plans can be large, return the count modulo 1000000007. Input Format: You are given an integer array nums and an integer target. Output Format: Return the number of subsets whose sum is exactly target, modulo 1000000007.
Examples
nums = [2, 3, 5, 6, 8, 10] target = 10
3
Explanation: Subsets reaching 10 are [10], [2, 8], [2, 3, 5]. Count = 3, so the output is 3.
Approach hint
Use a one-dimensional DP over sums.
Common mistake
Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.