Skip to main content

Construct the Lexicographically Largest Valid Sequence

搜索题,按照字典序回溯搜索就行

impl Solution {    pub fn construct_distanced_sequence(n: i32) -> Vec<i32> {        let mut res = vec![0;(n*2 - 1) as usize];        search(&mut res, (1<<n)-1, 0);        res    }}
fn search(arr: &mut Vec<i32>, n: usize, i: usize) -> bool {    if n == 0 {        return true;    }    if i >= arr.len() {        return false;    }    if arr[i] != 0 {        return search(arr, n, i + 1);    }
    for j in (1..=arr.len()).rev() {        if n&1 == 1 && j == 1 {            arr[i] = 1;            if search(arr, n^1, i + 1) {                return true;            }            arr[i] = 0;        }        if (n>>(j-1)) & 1 == 1 && i + j < arr.len() && arr[i + j] == 0 {            arr[i] = j as i32;            arr[i + j] = j as i32;            if search(arr, n^(1<<(j-1)), i + 1) {                return true;            }
            arr[i] = 0;            arr[i + j] = 0;        }    }        false}