Formatted question description: https://leetcode.ca/all/1718.html

# 1718. Construct the Lexicographically Largest Valid Sequence

## Level

Medium

## Description

Given an integer `n`

, find a sequence that satisfies all of the following:

- The integer
`1`

occurs once in the sequence. - Each integer between
`2`

and`n`

occurs twice in the sequence. - For every integer
`i`

between`2`

and`n`

, the**distance**between the two occurrences of`i`

is exactly`i`

.

The **distance** between two numbers on the sequence, `a[i]`

and `a[j]`

, is the absolute difference of their indices, `|j - i|`

.

Return *the lexicographically largest sequence. It is guaranteed that under the given constraints, there is always a solution*.

A sequence `a`

is lexicographically larger than a sequence `b`

(of the same length) if in the first position where `a`

and `b`

differ, sequence `a`

has a number greater than the corresponding number in `b`

. For example, `[0,1,9,0]`

is lexicographically larger than `[0,1,5,6]`

because the first position they differ is at the third number, and `9`

is greater than `5`

.

**Example 1:**

**Input:** n = 3

**Output:** [3,1,2,3,2]

**Explanation:** [2,3,2,1,3] is also a valid sequence, but [3,1,2,3,2] is the lexicographically largest valid sequence.

**Example 2:**

**Input:** n = 5

**Output:** [5,3,1,4,3,5,2,4,2]

**Constraints:**

`1 <= n <= 20`

## Solution

Use backtrack. Put the numbers into the sequence, from `n`

to 1, starting from the current index. For each index, always try the maximum possible number so that the sequence is the lexicographically largest one.

```
class Solution {
public int[] constructDistancedSequence(int n) {
int length = n * 2 - 1;
int[] sequence = new int[length];
Set<Integer> visited = new HashSet<Integer>();
backtrack(sequence, visited, 0, n, length);
return sequence;
}
public boolean backtrack(int[] sequence, Set<Integer> visited, int start, int n, int length) {
if (visited.size() == n)
return true;
if (sequence[start] > 0)
return backtrack(sequence, visited, start + 1, n, length);
for (int i = n; i > 0; i--) {
if (!visited.contains(i)) {
int next = start + i;
if (i == 1 || next < length && sequence[next] == 0) {
sequence[start] = i;
if (i > 1)
sequence[next] = i;
visited.add(i);
if (backtrack(sequence, visited, start + 1, n, length))
return true;
sequence[start] = 0;
if (i > 1)
sequence[next] = 0;
visited.remove(i);
}
}
}
return false;
}
}
```