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
We can first sort the array, which allows us to place duplicate numbers together, making it easier for us to remove duplicates.
Next, we design a function
- If
$i = n$ , it means we have finished filling in, add the current permutation to the answer array, and then return. - Otherwise, we enumerate the number
$nums[j]$ at the $i$th position, where the range of$j$ is$[0, n - 1]$ . We need to ensure that$nums[j]$ has not been used and is different from the number enumerated before, so as to ensure that the current permutation is not repeated. If the conditions are met, we can fill in$nums[j]$ , and continue to recursively fill in the next position, that is, call$dfs(i + 1)$ . After the recursive call ends, we need to mark$nums[j]$ as unused for later enumeration.
In the main function, we first sort the array, then call
The time complexity is
Similar problems:
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def dfs(i: int):
if i == n:
ans.append(t[:])
return
for j in range(n):
if vis[j] or (j and nums[j] == nums[j - 1] and not vis[j - 1]):
continue
t[i] = nums[j]
vis[j] = True
dfs(i + 1)
vis[j] = False
n = len(nums)
nums.sort()
ans = []
t = [0] * n
vis = [False] * n
dfs(0)
return ansclass Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> t = new ArrayList<>();
private int[] nums;
private boolean[] vis;
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
this.nums = nums;
vis = new boolean[nums.length];
dfs(0);
return ans;
}
private void dfs(int i) {
if (i == nums.length) {
ans.add(new ArrayList<>(t));
return;
}
for (int j = 0; j < nums.length; ++j) {
if (vis[j] || (j > 0 && nums[j] == nums[j - 1] && !vis[j - 1])) {
continue;
}
t.add(nums[j]);
vis[j] = true;
dfs(i + 1);
vis[j] = false;
t.remove(t.size() - 1);
}
}
}class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
vector<vector<int>> ans;
vector<int> t(n);
vector<bool> vis(n);
function<void(int)> dfs = [&](int i) {
if (i == n) {
ans.emplace_back(t);
return;
}
for (int j = 0; j < n; ++j) {
if (vis[j] || (j && nums[j] == nums[j - 1] && !vis[j - 1])) {
continue;
}
t[i] = nums[j];
vis[j] = true;
dfs(i + 1);
vis[j] = false;
}
};
dfs(0);
return ans;
}
};func permuteUnique(nums []int) (ans [][]int) {
sort.Ints(nums)
n := len(nums)
t := make([]int, n)
vis := make([]bool, n)
var dfs func(int)
dfs = func(i int) {
if i == n {
ans = append(ans, slices.Clone(t))
return
}
for j := 0; j < n; j++ {
if vis[j] || (j > 0 && nums[j] == nums[j-1] && !vis[j-1]) {
continue
}
vis[j] = true
t[i] = nums[j]
dfs(i + 1)
vis[j] = false
}
}
dfs(0)
return
}function permuteUnique(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const n = nums.length;
const ans: number[][] = [];
const t: number[] = new Array(n);
const vis: boolean[] = new Array(n);
const dfs = (i: number) => {
if (i === n) {
ans.push(t.slice());
return;
}
for (let j = 0; j < n; ++j) {
if (vis[j] || (j > 0 && nums[j] === nums[j - 1] && !vis[j - 1])) {
continue;
}
t[i] = nums[j];
vis[j] = true;
dfs(i + 1);
vis[j] = false;
}
};
dfs(0);
return ans;
}use std::collections::HashSet;
impl Solution {
fn dfs(i: usize, nums: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
let n = nums.len();
if i == n {
res.push(nums.clone());
return;
}
let mut set = HashSet::new();
for j in i..n {
if set.contains(&nums[j]) {
continue;
}
set.insert(nums[j]);
nums.swap(i, j);
Self::dfs(i + 1, nums, res);
nums.swap(i, j);
}
}
pub fn permute_unique(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut res = vec![];
Self::dfs(0, &mut nums, &mut res);
res
}
}public class Solution {
private List<IList<int>> ans = new List<IList<int>>();
private List<int> t = new List<int>();
private int[] nums;
private bool[] vis;
public IList<IList<int>> PermuteUnique(int[] nums) {
Array.Sort(nums);
int n = nums.Length;
vis = new bool[n];
this.nums = nums;
dfs(0);
return ans;
}
private void dfs(int i) {
if (i == nums.Length) {
ans.Add(new List<int>(t));
return;
}
for (int j = 0; j < nums.Length; ++j) {
if (vis[j] || (j > 0 && nums[j] == nums[j - 1] && !vis[j - 1])) {
continue;
}
vis[j] = true;
t.Add(nums[j]);
dfs(i + 1);
t.RemoveAt(t.Count - 1);
vis[j] = false;
}
}
}