题目描述
给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10
注意：本题与主站 47 题相同： https://leetcode.cn/problems/permutations-ii/
解法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res = []
path = [0] * n
used = [False] * n
nums.sort()
def dfs(u):
if u == n:
res.append(path.copy())
return
for i in range(n):
if used[i] or (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]):
continue
path[u] = nums[i]
used[i] = True
dfs(u + 1)
used[i] = False
dfs(0)
return res
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int n = nums.length;
boolean[] used = new boolean[n];
Arrays.sort(nums);
dfs(0, n, nums, used, path, res);
return res;
}
private void dfs(
int u, int n, int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
if (u == n) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < n; ++i) {
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
continue;
}
path.add(nums[i]);
used[i] = true;
dfs(u + 1, n, nums, used, path, res);
used[i] = false;
path.remove(path.size() - 1);
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> res;
vector<int> path(n, 0);
vector<bool> used(n, false);
sort(nums.begin(), nums.end());
dfs(0, n, nums, used, path, res);
return res;
}
void dfs(int u, int n, vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {
if (u == n) {
res.emplace_back(path);
return;
}
for (int i = 0; i < n; ++i) {
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
path[u] = nums[i];
used[i] = true;
dfs(u + 1, n, nums, used, path, res);
used[i] = false;
}
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | func permuteUnique(nums []int) [][]int {
n := len(nums)
res := make([][]int, 0)
path := make([]int, n)
used := make([]bool, n)
sort.Ints(nums)
dfs(0, n, nums, used, path, &res)
return res
}
func dfs(u, n int, nums []int, used []bool, path []int, res *[][]int) {
if u == n {
t := make([]int, n)
copy(t, path)
*res = append(*res, t)
return
}
for i := 0; i < n; i++ {
if used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
continue
}
path[u] = nums[i]
used[i] = true
dfs(u+1, n, nums, used, path, res)
used[i] = false
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 | using System.Collections.Generic;
using System.Linq;
public class Solution {
public IList<IList<int>> PermuteUnique(int[] nums) {
var results = new List<IList<int>>();
var temp = new List<int>();
var count = nums.GroupBy(n => n).ToDictionary(g => g.Key, g => g.Count());
Search(count, temp, results);
return results;
}
private void Search(Dictionary<int, int> count, IList<int> temp, IList<IList<int>> results)
{
if (!count.Any() && temp.Any())
{
results.Add(new List<int>(temp));
return;
}
var keys = count.Keys.ToList();
foreach (var key in keys)
{
temp.Add(key);
--count[key];
if (count[key] == 0) count.Remove(key);
Search(count, temp, results);
temp.RemoveAt(temp.Count - 1);
if (count.ContainsKey(key))
{
++count[key];
}
else
{
count[key] = 1;
}
}
}
}
|