All problems

Seat the Guests

Medium · backtracking

You are seating n guests, labelled 0 to n - 1, in a single row of n chairs. Some pairs of guests do not get along: the list clashes holds those pairs, and two guests from a pair must never sit in neighbouring chairs. Guests who are not neighbours can be anywhere, and a guest has no problem with anyone not named in clashes.

Return how many different seating orders (left-to-right sequences of all n guests) have no clashing pair sitting next to each other. Two orders are different if some chair holds a different guest, so reading the same row from the other end counts as a different order. A pair may be listed more than once, and in either order, such as [1, 0] and [0, 1].

Examples

Example 1

Input: n = 3, clashes = [[0, 1]]

Output: 2

Of the six orders, only 0 2 1 and 1 2 0 keep guests 0 and 1 apart, because guest 2 must sit between them.

Example 2

Input: n = 3, clashes = []

Output: 6

Nobody clashes, so all 3! = 6 orders count.

Example 3

Input: n = 2, clashes = [[0, 1]]

Output: 0

With only two chairs, the two guests are always neighbours.

Constraints