Odd and Even Taking Turns

Medium

Arrange the numbers from 1 to count in a row, using each exactly once, so that neighbours always differ in parity: an odd number is followed by an even one and vice versa. Return all such rows in lexicographic order (like words in a dictionary: compared by the first number where they differ).

Example 1

count=3 → [[1, 2, 3], [3, 2, 1]]

There are two odd numbers (1 and 3) and one even, so the odd ones take both ends: 1 2 3 and 3 2 1.

Example 2

count=1 → [[1]]

A single number makes a single row.

Example 3

count=4 → [[1, 2, 3, 4], [1, 4, 3, 2], [2, 1, 4, 3], [2, 3, 4, 1], [3, 2, 1, 4], [3, 4, 1, 2], [4, 1, 2, 3], [4, 3, 2, 1]]

Eight rows: a row may start with either an odd or an even number.

Constraints

1 ≤ count ≤ 10

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Backtracking

Similar problems

Weight Sets for an Exact Load Medium Card Hands for an Exact Total Medium All Orderings Medium Distinct Orderings With Repeats Medium Every Topping Combo Medium

Input

count=3

Expected

[[1, 2, 3], [3, 2, 1]]

Run checks the first 3 tests in your browser. Submit checks all 11 tests on the server, hidden ones included.