Abstract / Summary

Count the ways to play n unique songs exactly once in a playlist of length l from k songs using each song at most once per playlist.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 60% (100k+ submissions).

Typical patterns to solve this problem:

• Combinatorics
• Dynamic Programming
• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes the number of possible playlists that satisfy three constraints: the total number of distinct songs available (n), the desired length of the playlist (goal), and a restriction that a song cannot be replayed until at least k other songs have been played. The solution uses a depth-first recursion with memoization to explore all valid ways of arranging songs while respecting the “no recent repeat” rule. Results are returned modulo 1 000 000 007 to keep the numbers within integer limits.

Core Recursive Structure

At the heart of the algorithm is the nested function deeper, which receives two arguments: songs - the number of remaining positions to fill in the playlist, and unique - the count of distinct songs that have not yet been used in the current partial playlist. The function is decorated with @cache, which automatically stores previously computed results keyed by the pair (songs, unique).

@cache
def deeper(songs, unique):
    if songs == 0 and unique == 0:
        return 1                     # empty list is a valid completion
    if songs == 0 or unique == 0:
        return 0                     # impossible to finish under current state
    ...

The base cases capture two fundamental termination conditions. When both songs and unique are zero, the recursion has successfully built a complete playlist, contributing a single valid arrangement. If either dimension reaches zero while the other remains positive, the current path cannot lead to a valid playlist, and the function returns zero.

Transition Cases

The recursion proceeds by considering two mutually exclusive actions for the next slot in the playlist: replay an already used song, or introduce a new song that has not yet appeared.

Replaying an Existing Song

A replay is permissible only when the number of distinct songs already placed (unique) exceeds the cooldown threshold k. In that situation, the algorithm calculates the number of songs eligible for replay as unique - k. Each eligible song can be placed in the current position, after which the sub-problem reduces to filling songs-1 remaining slots while keeping the same count of distinct songs (unique).

if unique > k:
    choices = unique - k
    result = deeper(songs - 1, unique) * choices

Adding a New Song

When there are still songs that have never been used (n - unique), the algorithm may select one of them for the current slot. The number of possible new songs is unplayed = n - unique. The code adds one to this count because the recursive call expects the unique argument to represent the number of distinct songs still unavailable after the selection; therefore the call uses unique - 1.

unplayed = n - unique
if unplayed >= 0:
    choices = unplayed + 1
    result += deeper(songs - 1, unique - 1) * choices

Both branches accumulate their contributions in the local variable result. After exploring both possibilities, the function applies the required modulus before returning.

return result % 1_000_000_007

Edge Cases Handled

The implementation explicitly guards against several boundary conditions:

• The situation where the playlist length and the number of distinct songs to place are simultaneously zero, which represents a successfully completed construction.
• Scenarios where the remaining length is zero but there are still distinct songs left to place, or vice versa, both of which are impossible and immediately yield zero.
• The condition unique > k ensures that a replay is only considered when enough distinct songs have already been used to satisfy the cooldown requirement.
• The calculation unplayed = n - unique together with the check unplayed >= 0 guarantees that the algorithm never attempts to select a new song when all songs have already been used.

These checks prevent invalid recursive calls and keep the state space well-defined throughout the computation.

Memoization and Performance

The @cache decorator (available from functools) automatically stores the result of each distinct (songs, unique) pair. Because the recursion explores overlapping sub-problems-many different paths can lead to the same remaining length and distinct-song count-the cache eliminates redundant work by reusing previously computed values. This dramatically reduces the number of recursive invocations compared with a naïve exponential exploration.

The modulo operation is performed only once per recursive return, ensuring that intermediate products do not overflow Python’s arbitrary-precision integers while still preserving the final result modulo the required prime. By applying the modulus at the end of each call, the algorithm maintains correctness without incurring additional overhead inside the multiplication steps.

Overall Flow

The public method numMusicPlaylists simply forwards the initial parameters to the memoized helper, asking for the number of ways to fill goal slots while starting with all n songs still unused (unique = n). The final return value is the cached result of this top-level call, already reduced modulo 1 000 000 007.

return deeper(goal, n)

Through the combination of clear base cases, precise transition logic, and systematic caching, the code efficiently enumerates all valid playlists that satisfy the given constraints.

Imagine playing a game where you get to pick songs for a musical playlist. You have a total number of songs to choose from, and you want to make a playlist that is a certain length long. The tricky part is a rule that says if you want to play a song again, you have to wait for a few other different songs to play first.

The code acts like a very smart helper that looks at every possible way to build this list. It starts at the very end of the playlist and works backward to the first spot. At each step, it asks two questions. Can a song be repeated? If it can, it calculates how many choices are available based on the rule about waiting. Can a new song be played? If so, it looks at how many songs have not been picked yet and adds that to the list of possibilities.

Because there can be many, many ways to build the playlist, the code keeps track of the answers it already found. This saves a lot of time so it does not have to solve the same part of the puzzle over and over again. When it reaches the beginning, it knows exactly how many different playlists are possible. Since that number can grow to be truly massive, it keeps the final answer neat and tidy by using a large number to split the result down.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python				TS
	WalkCCC	C++		Java
	leetcode.ca	C++		Java	Go	Python			Rust	TS
	LeetcodeHelp	C++		Java		Python
	Progiez	C++		Java		Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	gouthampradhan			Java
	halfrost				Go
	JoshCrozier		JS
	lkwq007					Python
	muhammadfarhankt				Go
	suxrobGM						C#
	vli02							C
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
muhammadfarhankt	Go
suxrobGM	C#
vli02	C
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality