920. Number of Music Playlists

link

Generalize the song

class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:

        MOD = 10 ** 9 + 7

        @cache
        def backtrack(s, left):
            if left == 0:
                if s == n:
                    return 1
                return 0
            
            total = 0

            # pick different one
            if s < n:
                total += (n - s) * backtrack(s+1, left - 1)

            # pick from used one
            if s > k:
                # ?? tricky (to ensure there are at least k songs between repeated songs)
                total += (s - k) * backtrack(s, left - 1)

            return total % MOD

        return backtrack(0 ,goal) % MOD