## 1718. Construct the Lexicographically Largest Valid Sequence

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 = 3Output:[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 = 5Output:[5,3,1,4,3,5,2,4,2]

**Constraints:**

`1 <= n <= 20`

## Rust Solution

```
struct Solution;
impl Solution {
fn construct_distanced_sequence(n: i32) -> Vec<i32> {
let mut nums: Vec<i32> = vec![];
for i in (2..=n).rev() {
nums.push(i);
}
nums.push(1);
let n = n as usize;
let m = 2 * n - 1;
let mut cur = vec![0; m];
let mut visited: u32 = (1 << n) - 1;
Self::dfs(0, &mut cur, &mut visited, &nums, m, n);
cur
}
fn dfs(
start: usize,
cur: &mut Vec<i32>,
visited: &mut u32,
nums: &[i32],
m: usize,
n: usize,
) -> bool {
if start == m {
true
} else {
if cur[start] == 0 {
for i in 0..n {
if 1 << i & *visited != 0 {
let distance = nums[i] as usize;
if distance == 1 {
*visited &= !(1 << i);
cur[start] = nums[i];
let found = Self::dfs(start + 1, cur, visited, nums, m, n);
if found {
return true;
}
cur[start] = 0;
*visited |= 1 << i;
} else {
if start + distance < m && cur[start + distance] == 0 {
cur[start] = nums[i];
cur[start + distance] = nums[i];
*visited &= !(1 << i);
let found = Self::dfs(start + 1, cur, visited, nums, m, n);
if found {
return true;
}
cur[start + distance] = 0;
cur[start] = 0;
*visited |= 1 << i;
}
}
}
}
false
} else {
Self::dfs(start + 1, cur, visited, nums, m, n)
}
}
}
}
#[test]
fn test() {
let n = 3;
let res = vec![3, 1, 2, 3, 2];
assert_eq!(Solution::construct_distanced_sequence(n), res);
let n = 5;
let res = vec![5, 3, 1, 4, 3, 5, 2, 4, 2];
assert_eq!(Solution::construct_distanced_sequence(n), res);
}
```

Having problems with this solution? Click here to submit an issue on github.