LeetCode 2585 - Number of Ways to Earn Points

This problem is essentially asking how many distinct ways we can select questions from multiple types to reach exactly a target score. Each type of question has a fixed number of questions (counti) and a fixed number of points per question (marksi).

leetcodehardarraydynamic-programming

LeetCode Problem 2585

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

This problem is essentially asking how many distinct ways we can select questions from multiple types to reach exactly a target score. Each type of question has a fixed number of questions (counti) and a fixed number of points per question (marksi). Questions of the same type are indistinguishable, which means selecting any subset of questions of the same type with the same quantity counts as one way.

The input consists of an integer target and a 2D array types where each subarray [counti, marksi] represents the number of questions and points per question for that type. The output is the total number of ways to reach exactly the target points, modulo 10^9 + 7.

The constraints indicate that target can be up to 1000, and there can be up to 50 types of questions, each with up to 50 questions. This suggests that naive combinatorial enumeration is infeasible because the number of combinations grows exponentially. Edge cases include situations where the target is smaller than the lowest possible combination, exactly equal to the sum of all maximum points, or when some types have more questions than needed.

Approaches

A brute-force approach would involve recursively trying all combinations of questions from each type. For each type, we could choose 0 up to counti questions and recursively attempt to achieve the remaining target with subsequent types. While correct, this approach is too slow since the number of recursive calls is exponential in both the number of types and the number of questions per type.

The optimal approach is dynamic programming. The key insight is to recognize this as a bounded knapsack problem: each question type can contribute multiple times to the total, but only up to its count. We can use a 1D DP array dp[j] where j represents a score from 0 to target. Initially, dp[0] = 1 because there is exactly one way to achieve zero points: select no questions. Then, for each type, we iterate from target down to 0, and for each possible number of questions of that type, update the ways to achieve a new score.

Using DP with careful iteration ensures we count all combinations without redundancy and stay within feasible time complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O((count1+1)(count2+1)...*(countn+1)) O(target) Exponentially many combinations; infeasible for constraints
Optimal O(n * target * max_count) O(target) Bounded knapsack DP with rolling array optimization

Algorithm Walkthrough

  1. Initialize a DP array of size target + 1 with dp[0] = 1 and all other values 0. This represents the number of ways to achieve each score.

  2. For each type [counti, marksi]:

  3. Iterate j from target down to 0. This reverse iteration prevents overcounting within the same type.

  4. For each k from 1 to counti:

  5. Compute next_score = j + k * marksi.

  6. If next_score > target, break because larger scores are not needed.

  7. Update dp[next_score] = (dp[next_score] + dp[j]) % MOD.

  8. After processing all types, dp[target] contains the total number of ways to reach the exact target score.

Why it works: This algorithm correctly maintains the invariant that dp[j] represents the total number of ways to achieve score j using the types processed so far. By iterating in reverse and considering all counts per type, we account for all valid combinations without overcounting.

Python Solution

from typing import List

class Solution:
    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:
        MOD = 10**9 + 7
        dp = [0] * (target + 1)
        dp[0] = 1
        
        for count, marks in types:
            for j in range(target, -1, -1):
                for k in range(1, count + 1):
                    next_score = j + k * marks
                    if next_score > target:
                        break
                    dp[next_score] = (dp[next_score] + dp[j]) % MOD
        return dp[target]

Explanation: The dp array keeps track of the number of ways to reach each possible score. For each type, we iterate in reverse to avoid using the same type multiple times in one iteration. The inner loop goes over possible counts for that type, updating all achievable scores. Modular arithmetic ensures we stay within the required numeric limits.

Go Solution

func waysToReachTarget(target int, types [][]int) int {
    const MOD int = 1e9 + 7
    dp := make([]int, target+1)
    dp[0] = 1

    for _, t := range types {
        count, marks := t[0], t[1]
        for j := target; j >= 0; j-- {
            for k := 1; k <= count; k++ {
                nextScore := j + k*marks
                if nextScore > target {
                    break
                }
                dp[nextScore] = (dp[nextScore] + dp[j]) % MOD
            }
        }
    }
    return dp[target]
}

Explanation: The Go solution mirrors the Python approach, using a slice for the DP array and constants for modular arithmetic. Reverse iteration is used for correctness, and the inner loop breaks early when scores exceed the target.

Worked Examples

Example 1

target = 6, types = [[6,1],[3,2],[2,3]]

  1. Start with dp = [1,0,0,0,0,0,0]
  2. Process [6,1]:
  • Adding 1 question 1 point: dp[1] = 1
  • Adding 2 questions 1 point each: dp[2] = 1
  • … dp[6] = 1
  1. Process [3,2]:
  • Combining with previous dp values to update dp[2], dp[4], dp[6], etc.
  1. Process [2,3]:
  • Updates dp[3], dp[6] by adding new combinations.
  1. Final dp[6] = 7

Complexity Analysis

Measure Complexity Explanation
Time O(n * target * max_count) n types, target scores, and at most max_count questions per type
Space O(target) Only a 1D array of size target + 1 is needed

The reverse iteration and modular arithmetic keep updates efficient and prevent overcounting, keeping memory usage minimal.

Test Cases

# Provided examples
assert Solution().waysToReachTarget(6, [[6,1],[3,2],[2,3]]) == 7
assert Solution().waysToReachTarget(5, [[50,1],[50,2],[50,5]]) == 4
assert Solution().waysToReachTarget(18, [[6,1],[3,2],[2,3]]) == 1

# Edge cases
assert Solution().waysToReachTarget(1, [[1,1]]) == 1 # minimum target
assert Solution().waysToReachTarget(1000, [[50,20],[50,15]]) >= 0 # large target, many combinations
assert Solution().waysToReachTarget(5, [[1,1],[1,2],[1,3]]) == 1 # exact fit without excess
Test Why
target=6, multiple types Validates standard combination counting
target=5, large counts Validates algorithm handles large counts efficiently
target=18, exact sum Validates exact fit with all questions
target=1, single question Minimal input edge case
target=1000, large numbers Stress test with large target
target=5, small counts Ensures correct handling of limited options

Edge Cases

  1. Minimum target and single type: If target = 1 and types = [[1,1]], the algorithm correctly identifies one way. This is important because DP initialization must handle dp[0] = 1 to ensure a base case exists.
  2. Maximum target with multiple large types: When target is large and types have counts up to 50, nested loops could potentially be slow. The DP approach avoids exponential recursion and handles this efficiently within constraints.
  3. Target not achievable: If no combination of questions can sum to target, the DP array will leave dp[target] = 0. The algorithm correctly returns zero without needing explicit checks.

This approach guarantees correctness, efficiency, and handles edge cases gracefully.