47. Permutations II

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

 

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

 

Constraints:

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

Rust Solution

struct Solution;

impl Solution {
    fn permute_unique(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        let n = nums.len();
        let mut res: Vec<Vec<i32>> = vec![];
        let mut used: Vec<bool> = vec![false; n];
        let mut cur: Vec<i32> = vec![];
        nums.sort_unstable();
        Self::dfs(&mut cur, &mut used, &mut res, &nums, n);
        res
    }

    fn dfs(
        cur: &mut Vec<i32>,
        used: &mut Vec<bool>,
        all: &mut Vec<Vec<i32>>,
        nums: &[i32],
        n: usize,
    ) {
        if cur.len() == n {
            all.push(cur.to_vec());
        } else {
            for i in 0..n {
                if used[i] {
                    continue;
                }
                if i > 0 && nums[i] == nums[i - 1] && !used[i - 1] {
                    continue;
                }
                used[i] = true;
                cur.push(nums[i]);
                Self::dfs(cur, used, all, nums, n);
                used[i] = false;
                cur.pop();
            }
        }
    }
}

#[test]
fn test() {
    let nums = vec![1, 1, 2];
    let mut res = vec_vec_i32![[1, 1, 2], [1, 2, 1], [2, 1, 1]];
    let mut ans = Solution::permute_unique(nums);
    res.sort();
    ans.sort();
    assert_eq!(ans, res);
    let nums = vec![2, 2, 1, 1];
    let mut res = vec_vec_i32![
        [1, 1, 2, 2],
        [1, 2, 1, 2],
        [1, 2, 2, 1],
        [2, 1, 1, 2],
        [2, 1, 2, 1],
        [2, 2, 1, 1]
    ];
    let mut ans = Solution::permute_unique(nums);
    res.sort();
    ans.sort();
    assert_eq!(ans, res);
}

Having problems with this solution? Click here to submit an issue on github.