There is a test that has n types of questions. You are given an integer target and a 0-indexed 2D integer array types where types[i] = [counti, marksi] indicates that there are counti questions of the ith type, and each one of them is worth marksi points.
Return the number of ways you can earn exactly target points in the exam. Since the answer may be too large, return it modulo 109 + 7.
Note that questions of the same type are indistinguishable.
3 questions of the same type, then solving the 1st and 2nd questions is the same as solving the 1st and 3rd questions, or the 2nd and 3rd questions.Example 1:
Input: target = 6, types = [[6,1],[3,2],[2,3]] Output: 7 Explanation: You can earn 6 points in one of the seven ways: - Solve 6 questions of the 0th type: 1 + 1 + 1 + 1 + 1 + 1 = 6 - Solve 4 questions of the 0th type and 1 question of the 1st type: 1 + 1 + 1 + 1 + 2 = 6 - Solve 2 questions of the 0th type and 2 questions of the 1st type: 1 + 1 + 2 + 2 = 6 - Solve 3 questions of the 0th type and 1 question of the 2nd type: 1 + 1 + 1 + 3 = 6 - Solve 1 question of the 0th type, 1 question of the 1st type and 1 question of the 2nd type: 1 + 2 + 3 = 6 - Solve 3 questions of the 1st type: 2 + 2 + 2 = 6 - Solve 2 questions of the 2nd type: 3 + 3 = 6
Example 2:
Input: target = 5, types = [[50,1],[50,2],[50,5]] Output: 4 Explanation: You can earn 5 points in one of the four ways: - Solve 5 questions of the 0th type: 1 + 1 + 1 + 1 + 1 = 5 - Solve 3 questions of the 0th type and 1 question of the 1st type: 1 + 1 + 1 + 2 = 5 - Solve 1 questions of the 0th type and 2 questions of the 1st type: 1 + 2 + 2 = 5 - Solve 1 question of the 2nd type: 5
Example 3:
Input: target = 18, types = [[6,1],[3,2],[2,3]] Output: 1 Explanation: You can only earn 18 points by answering all questions.
Constraints:
1 <= target <= 1000n == types.length1 <= n <= 50types[i].length == 21 <= counti, marksi <= 50The problem can be modeled as a bounded knapsack dynamic programming task. Each question type provides a certain number of questions (count), and each question contributes a fixed number of points (marks). The goal is to compute how many distinct ways we can reach exactly the target score while respecting the limit on how many questions of each type can be chosen.
A common approach is to use dynamic programming where dp[i] represents the number of ways to achieve exactly i points. For every question type, we update the DP array by considering selecting 0 to count questions of that type, ensuring the total score does not exceed the target. To avoid counting duplicates, updates are typically done in reverse order of scores.
This technique resembles the classic bounded knapsack problem. Since the number of question types and the target score are limited, the DP approach efficiently enumerates valid combinations. Modulo arithmetic (usually 1e9+7) is used to keep results within bounds.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bounded Knapsack DP | O(n * target * count) | O(target) |
| Optimized DP with Prefix/Sliding Window | O(n * target) | O(target) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Use Dynamic Programming
Let ways[i][points] be the number of ways to score a given number of points after solving some questions of the first i types.
ways[i][points] is equal to the sum of ways[i-1][points - solved * marks[i] over 0 <= solved <= count_i
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems involving bounded knapsack and dynamic programming patterns are common in technical interviews, including FAANG-style rounds. This problem helps test optimization, DP transitions, and constraint handling.
The optimal approach uses dynamic programming similar to a bounded knapsack problem. We track how many ways we can reach each score up to the target while considering the limited number of questions in each type.
The difficulty comes from combining bounded choices with counting combinations efficiently. Without a well-structured DP strategy, brute-force approaches quickly become infeasible due to exponential combinations.
A dynamic programming array is the most effective structure. It stores the number of ways to achieve each intermediate score and is updated as each question type is processed.