Frontend School

Content Playlist Combinations

DSA
medium

Content Playlist Combinations

Medium
Backtracking
Arrays
String

Overview

Sharechat users love creating engaging video playlists. To help users discover new content, we're building a feature that suggests sequences of video topics that sum up to a specific duration. This problem challenges you to find all such valid topic sequences.

What you need to do / Task

Implement a function findPlaylistCombinations that takes a list of available video clips (each described by its topic and duration) and a targetDuration. The function should return all unique sequences of clip topics whose total duration exactly matches targetDuration.

Input & output

  • clips: An array of objects, where each object has two properties: topic (string) and duration (number).
  • targetDuration: A number representing the exact total duration the playlist must have.
  • Return: A string[][] (array of arrays of strings), where each inner array represents a valid sequence of clip topics. The order of topics within a sequence matters. The order of sequences in the output array does not matter.

Clarifications

  • Clips can be reused multiple times within a single playlist sequence.
  • If no combinations are found, return an empty array.
  • All duration values will be positive integers.

Examples

1

Example 1

Input:

clips = [{"topic":"comedy","duration":10},{"topic":"drama","duration":15}], targetDuration = 25

Output:

[["comedy","drama"],["drama","comedy"]]

Note:

"comedy" (10) + "drama" (15) = 25. "drama" (15) + "comedy" (10) = 25. These are two distinct sequences.

2

Example 2

Input:

clips = [{"topic":"short","duration":5},{"topic":"medium","duration":10}], targetDuration = 15

Output:

[["short","short","short"],["short","medium"],["medium","short"]]

Note:

  • "short" (5) + "short" (5) + "short" (5) = 15
  • "short" (5) + "medium" (10) = 15
  • "medium" (10) + "short" (5) = 15
3

Example 3

Input:

clips = [{"topic":"news","duration":20}], targetDuration = 10

Output:

[]

Note:

No combination of "news" clips can sum up to 10.

Constraints

Constraints & assumptions

  • 1 <= clips.length <= 15
  • 1 <= topic.length <= 10
  • 1 <= duration <= 100
  • 1 <= targetDuration <= 500
  • Topics are unique strings within the clips array.
  • The clips array will not be empty.

What interviewers evaluate

  • Correctness and completeness of the backtracking algorithm.
  • Ability to handle state management (current duration, current path) effectively.
  • Time and space complexity analysis and optimization (e.g., pruning).
  • Code clarity, structure, and edge case handling.

Loading editor...