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 <= 50Problem Overview: You are given several question types where each type provides a fixed number of points and can be used a limited number of times. The goal is to count how many different combinations of questions reach exactly the target score. Order does not matter, so this becomes a bounded combination counting problem.
Approach 1: Recursive Dynamic Programming with Memoization (Time: O(n * target * count), Space: O(n * target))
Treat the problem as a decision process across question types. At index i, decide how many questions of the current type to take (from 0 to count[i]). Each choice subtracts k * marks[i] from the remaining score and recursively processes the next type. Without caching, this creates many repeated subproblems. Memoization stores results for states defined by (index, remainingScore). This converts the exponential recursion into a polynomial solution. The approach is intuitive and mirrors the combinational search directly, which helps when reasoning about constraints and correctness.
This solution relies heavily on overlapping subproblems and is a classic application of dynamic programming. The input structure is stored in an array of types, and recursion iterates through each type while tracking the remaining score.
Approach 2: Dynamic Programming with State Compression (Bounded Knapsack) (Time: O(n * target * count), Space: O(target))
This problem maps directly to the bounded knapsack counting pattern. Let dp[s] represent the number of ways to reach score s. Initialize dp[0] = 1. For each question type, iterate scores from target down to 0. For every possible number of questions k from 1 to the allowed count, update dp[s] using dp[s - k * marks] if the score remains valid.
Iterating scores backward prevents reuse of the same question type more times than allowed. This effectively compresses the 2D DP state (type, score) into a single dimension. The memory usage drops to O(target), which is efficient for the constraint where the target score can be up to around 1000.
Recommended for interviews: The state-compressed dynamic programming solution is what interviewers typically expect. It demonstrates recognition of the bounded knapsack pattern and efficient space optimization. The recursive memoized version is still valuable during explanation because it clearly shows the decision structure before converting it into iterative DP.
This approach uses a dynamic programming (DP) technique to determine the number of different ways to achieve the target score. We use a 1D DP array where dp[j] represents the number of ways to achieve a score of j.
dp with dp[0] set to 1 (one way to score zero points) and the rest to 0.This approach uses state compression to keep the memory usage low by maintaining only scores that are still reachable given the constraints.
The C implementation initializes a dp array of size target + 1, filled initially with zeroes and sets dp[0] to 1, representing one way to achieve a score of zero by not solving any questions.
The nested loops iterate through each question type and update the possible scores in the dp array, considering the number of each type of question and their respective scores.
Time Complexity: O(n * target * countmax)
Space Complexity: O(target), where countmax is the maximum count of questions of any type.
This approach utilizes recursion with memoization to explore all possible combinations of question types to achieve the target score. Each recursive call evaluates if it's possible to achieve the remaining score using the current and subsequent question types. Memoization is used to store results of subproblems to avoid re-computation.
In this Python solution, recursion with memoization is used to explore different scores. The dp() function considers each possible number of questions of a current type and recursively attempts to reach the target by calling itself with a decreased target and incremented index. Memoization efficiently caches computed results for quicker access.
Time Complexity: O(n * target * countmax) in the worst case, due to solving subproblems.
Space Complexity: O(n * target) due to recursion and memoization storage.
We define f[i][j] to represent the number of methods to get j points exactly from the first i types of questions. Initially, f[0][0] = 1, and the rest f[i][j] = 0. The answer is f[n][target].
We can enumerate the ith type of questions, suppose the number of questions of this type is count, and the score is marks. Then we can get the following state transition equation:
$
f[i][j] = sum_{k=0}^{count} f[i-1][j-k times marks]
where k represents the number of questions of the ith type.
The final answer is f[n][target]. Note that the answer may be very large and needs to be modulo 10^9 + 7.
The time complexity is O(n times target times count) and the space complexity is O(n times target). n is the number of types of questions, and target and count$ are the target score and the number of questions of each type, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming with State Compression | Time Complexity: O(n * target * countmax) |
| Recursive Dynamic Programming with Memoization | Time Complexity: O(n * target * countmax) in the worst case, due to solving subproblems. |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DP with Memoization | O(n * target * count) | O(n * target) | When reasoning about the problem recursively or explaining the state transition during interviews |
| Dynamic Programming with State Compression (Bounded Knapsack) | O(n * target * count) | O(target) | Preferred production and interview solution due to lower memory usage and clean iterative implementation |
Number of Ways to Earn Points || Dynamic Programming Knapsack || Leetcode-2585 • Aryan Mittal • 1,352 views views
Watch 9 more video solutions →Practice Number of Ways to Earn Points with our built-in code editor and test cases.
Practice on FleetCode