Permutations

Array Backtracking

81.7% acceptance

Jan 12, 2026

20746

383

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    let mut current = Vec::new();
    let mut used = vec![false; nums.len()];
    Self::backtrack_permute(&nums, &mut current, &mut used, &mut result);
    result
  }
  
  fn backtrack_permute(nums: &Vec<i32>, current: &mut Vec<i32>, used: &mut Vec<bool>, result: &mut Vec<Vec<i32>>) {
    if current.len() == nums.len() {
      result.push(current.clone());
      return;
    }
    
    for i in 0..nums.len() {
      if used[i] {
        continue;
      }
      
      current.push(nums[i]);
      used[i] = true;
      Self::backtrack_permute(nums, current, used, result);
      used[i] = false;
      current.pop();
    }
  }
}