Permutations iii

Array Backtracking

87.0% acceptance

Mar 31, 2026

Given an integer n, an alternating permutation is a permutation of the first n positive integers such that no two adjacent elements are both odd or both even. Return all such alternating permutations sorted in lexicographical order.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn permute(n: i32) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    let mut perm = Vec::with_capacity(n as usize);
    let mut used = vec![false; n as usize + 1];
    Self::backtrack(n, &mut perm, &mut used, &mut result);
    result
  }

  fn backtrack(n: i32, perm: &mut Vec<i32>, used: &mut Vec<bool>, result: &mut Vec<Vec<i32>>) {
    if perm.len() == n as usize {
      result.push(perm.clone());
      return;
    }
    for v in 1..=n {
      if used[v as usize] { continue; }
      if let Some(&last) = perm.last() {
        if (last % 2) == (v % 2) { continue; }
      }
      perm.push(v);
      used[v as usize] = true;
      Self::backtrack(n, perm, used, result);
      perm.pop();
      used[v as usize] = false;
    }
  }
}