Solution is a greedy recursion. Iterate in reverse order to make sure to get the largest solution first.
function constructDistancedSequence(n: number): number[] {
const size = 2 * n - 1;
const result: number[] = new Array(size).fill(0);
const used: boolean[] = new Array(n + 1).fill(false);
function backtrack(index: number): boolean {
if (index === size) return true; // If we filled the array, return success
if (result[index] !== 0) return backtrack(index + 1); // Skip filled positions
for (let num = n; num >= 1; num--) { // Try from largest to smallest
if (used[num]) continue;
if (num === 1) {
// Place 1 (only once)
result[index] = 1;
used[1] = true;
if (backtrack(index + 1)) return true;
used[1] = false;
result[index] = 0;
} else {
// Place num at index and index + num (if valid)
if (index + num < size && result[index + num] === 0) {
result[index] = result[index + num] = num;
used[num] = true;
if (backtrack(index + 1)) return true;
used[num] = false;
result[index] = result[index + num] = 0;
}
}
}
return false;
}
backtrack(0);
return result;
}