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 = 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`

1718. Construct the Lexicographically Largest Valid Sequence
``````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);
}
``````