Feature #9: Movie Combinations of a Genre

Description

Suppose we have $n$ different movie genres like Action, Comedy, Family, Horror, and so on. In each genre, we have $0$ to $k$ movies. We need to screen several movies of different genres in a specific sequence. For example, in the morning, may want to feature a Family program, followed by a Comedy. Late at night, we may want to show Horror movies followed by Action movies. At prime time, we may want to use some other sequence.

Our task is to implement an algorithm that creates a combination of movies, chosen from the given set of genres in a specific sequence.

Let’s say we have the following genres with the following movies in each genre:

If we have the movies given in the example above and the input to our algorithm is ["Family", "Action"], then it should return the following list containing all of the possible combinations of a Family movie followed by an Action movie, chosen from the available data.

["Frozen;Iron Man;","Frozen;Wonder Woman;","Frozen;Avengers;","Kung fu Panda;Iron Man;","Kung fu Panda;Wonder Woman;","Kung fu Panda;Avengers;","Ice Age;Iron Man;","Ice Age;Wonder Woman;","Ice Age;Avengers;"]

Note: We add a semicolon (;) just to separate the movie names.

Solution

To solve this problem, we can use a backtracking algorithm template to generate all of the possible combinations correctly.

Let’s break down this problem into four parts.

• If the input has only one genre, return all the movies in that genre—for example, ["Action"]. This example is trivial where all of the corresponding movies will be returned, for example, ["Iron Man", "Wonder Woman", "Avengers"].

• We already know how to solve the one-genre problem. To solve the two-genre problem, such as ["Action, Family"], we can pick the one-genre solutions for the Action genre and then append the solutions for the one-genre problem of the Family genre. For example, start with "Iron Man" and then append all the solutions for the one-genre problem of the Family genre, resulting in [[Iron Man, Frozen],[Iron Man, Kung Fu Panda],[Iron Man, Ice Age]]. Then, we can switch to the other solutions for the one-genre problem of the Action ...