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`

47. Permutations II
``````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);
}
``````