You have exactly n minutes of free time and a set of allowed break lengths (reusable).
Return the number of distinct ordered sequences of breaks that fill the time exactly.
Two sequences with the same lengths in a different order count separately.
breakTime(n, lengths)
Input format: n | lengths.
n=3, lengths=[1, 2] // → 3 (1+1+1, 1+2, 2+1)
n=4, lengths=[1, 2] // → 5
n=0, lengths=[1] // → 1 (the empty sequence)
This asks for a count of ordered sequences, not the sequences themselves, but the exploration is still a decision tree: at each moment, some time is left, and you decide the next break. Since order matters (1+2 and 2+1 are different sequences using the same lengths), this is about the order of use, not just which lengths.
Given some remaining time, how many distinct ordered sequences sum exactly to it? A smaller version of the same question.
Remaining time of 0 has exactly one way: take no more breaks — the empty sequence counts as one valid way, not zero.
Negative remaining time means you overshot — zero ways.
Otherwise, the first break must be one of the allowed lengths. Whichever you pick, the rest must fill the remaining time after subtracting it. So the total is the sum, over every allowed length, of ways to fill (remaining minus that length).
The recursion fixes the next break, not a set of lengths to use. Counting which lengths appear and multiplying by orderings would require handling repeated lengths and multiset permutation counts — fiddly. Asking "what's the very next break" instead means different branches (first break = 1 vs. 2) can never produce the same sequence, since sequences starting differently are different. That's why 1+2 and 2+1 come out as separate counts.
Every valid sequence has some first element, one of the allowed lengths — summing over all of them covers every sequence exactly once, since fixing the first break makes the rest a strictly smaller, well-defined subproblem. The recursion shrinks remaining time by at least the smallest break length each call, so it terminates.
This recomputes the same remaining-time subproblems many times when different paths land on the same total (1+2 and 2+1 both need to solve for 0), so runtime grows exponentially with the number of breaks. Memoizing by remaining time would eliminate that redundancy, but the core "sum over the choice of next break" logic stays the same.
def break_time(n, lengths):
if n == 0:
return 1
if n < 0:
return 0
total = 0
for l in lengths:
total += break_time(n - l, lengths)
return total
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.