Permutations ii

Array Backtracking Sorting

63.0% acceptance

Jan 12, 2026

9109

163

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn permute_unique(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    let mut nums = nums;
    nums.sort();
    let mut used = vec![false; nums.len()];
    let mut current = Vec::new();
    Self::backtrack_unique(&nums, &mut used, &mut current, &mut result);
    result
  }
  
  fn backtrack_unique(nums: &Vec<i32>, used: &mut Vec<bool>, current: &mut Vec<i32>, 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;
      }
      // Skip duplicates: if current element is same as previous and previous is not used
      if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
        continue;
      }
      
      used[i] = true;
      current.push(nums[i]);
      Self::backtrack_unique(nums, used, current, result);
      current.pop();
      used[i] = false;
    }
  }
}