Maximize Combo Segments
Context
In the arcade game Neon Dash, a combo meter has a target number of points to fill. Each legal move adds one of the permitted positive point amounts, and moves may be repeated. Determine the largest number of moves that fills the meter exactly. If no sequence reaches the target, report failure.
Problem
Write a function that finds the maximum number of moves whose point gains sum exactly to target_points. Each value in move_lengths is a permitted positive gain, and any permitted gain may be used repeatedly. The order of moves does not affect the result. Return the greatest possible move count for an exact total. If target_points cannot be formed, return -1. A target of zero is already complete and requires zero moves.
Examples
move_lengths = [2, 3, 5]target_points = 115move_lengths = [4, 6]target_points = 7-1move_lengths = [1, 3, 5]target_points = 00Constraints
0 <= target_points <= 5001 <= len(move_lengths) <= 201 <= move_lengths[i] <= 500 for every i- Types:
target_pointsis int,move_lengthsis int[]; result is int
Function signature
def max_combo_moves(target_points: int, move_lengths: list[int]) -> int
target_pointsint- The exact number of combo points to fill.
move_lengthslist[int]- Positive point gains available for individual moves; each gain can be reused.
- returns int
- The maximum number of moves whose gains total exactly target_points, or -1 when no exact total is possible.
Adapted from MBPP problem task_971 (CC BY 4.0). Rewritten, extended and verified by Iksha.
Notes
- Repeated move lengths are allowed and must not change the correct result.
- A move length larger than the target may be ignored naturally.