Finishing combo sequences

Write codeMedium14 min

Your task

In a fighting game, each attack in your move list deals a fixed amount of damage, and you may repeat attacks freely. A finishing combo must deal exactly the boss's remaining health, no overkill. Given the list of distinct positive damage values and the boss health, return how many distinct ordered sequences of attacks deal exactly that total. The same attacks in a different order count as different combos. If health is 0, return 1 (the empty combo).

Examples

count_finishing_combos(damages: list[int], health: int) -> int
Example 1
Inputcount_finishing_combos([1, 2], 4)
Output5
Example 2
Inputcount_finishing_combos([2, 3], 7)
Output3