来源：力扣（LeetCode）
链接: https://leetcode.cn/problems/permutations-ii/
给定一个可包含重复数字的序列 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
本题的区别是相同元素的重复组合需要进行过滤，相同元素可以使用排序以及哈希表进行过滤处理。排序就是相邻元素如果相同的话且前一个进行处理后，下一个相同元素就不进行处理；
- 递归: 遍历元素，剩余的列表元素按照同样的方法求得组合，再对组合进行遍历，将左边遍历的元素加入到每种组合的前面作为最终的一种组合，再将该组合放入到结果列表中；
- 回溯：按顺序枚举每一位可能出现的情况，已经选择的数字在 当前 要选择的数字中不能出现。按照这种策略搜索就能够做到 不重不漏。
python实现
- 排序
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
if n == 1:
return [nums]
res = []
nums.sort()
for i in range(n):
if i > 0 and nums[i] == nums[i-1]:
continue
left_num = nums[i]
right_parts = self.permuteUnique(nums[:i]+nums[i+1:])
for part in right_parts:
res.append([left_num]+part)
return res
- 哈希表
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
if n == 1:
return [nums]
res = {}
for i in range(n):
if i > 0 and nums[i] == nums[i-1]:
continue
left_num = nums[i]
right_parts = self.permuteUnique(nums[:i]+nums[i+1:])
for part in right_parts:
res[tuple([left_num]+part)] = ''
return [list(k) for k in res]
c++实现
- 排序
class Solution {
public:
vector> permuteUnique(vector& nums) {
int n = nums.size();
if (n == 1)
return {nums};
vector> res;
sort(nums.begin(), nums.end());
for (int i=0; i
if (i > 0 && nums[i] == nums[i-1])
continue;
int left_num = nums[i];
vector tmp_num = nums;
tmp_num.erase(tmp_num.begin()+i);
vector> right_parts = permuteUnique(tmp_num);
for(vector part: right_parts) {
part.insert(part.begin(), left_num);
res.push_back(part);
}
}
return res;
}
};
- 哈希表
class Solution {
public:
vector> permuteUnique(vector& nums) {
int n = nums.size();
if (n == 1)
return {nums};
map, int> res1;
vector> res2;
for (int i=0; i
if (i > 0 && nums[i] == nums[i-1])
continue;
int left_num = nums[i];
vector tmp_num = nums;
tmp_num.erase(tmp_num.begin()+i);
vector> right_parts = permuteUnique(tmp_num);
for(vector part: right_parts) {
part.insert(part.begin(), left_num);
auto it = res1.find(part);
if (it == res1.end()) {
res1[part] = 0;
res2.push_back(part);
}
}
}
return res2;
}
};
复杂度分析
- 时间复杂度： O ( N ∗ N ! ) O(N*N!) O(N∗N!)
- 空间复杂度： O ( N ) O(N) O(N)
python实现
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
if n == 1:
return [nums]
nums.sort()
res = []
used = [False for _ in range(n)]
def dfs(nums, size, depth, path, used):
if depth == size:
res.append(path.copy())
return
for i in range(size):
if not used[i]:
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
used[i] = True
path.append(nums[i])
dfs(nums, size, depth+1, path, used)
used[i] = False
path.pop()
dfs(nums, n, 0, [], used)
return res
c++实现
class Solution {
private:
vector> res;
public:
void dfs(vector& nums, int depth, int size, vector path, vector used) {
if (depth == size) {
res.push_back(path);
return;
}
for (int i=0; i
if (!used[i]) {
if (i > 0 && nums[i] == nums[i-1] && !used[i-1])
continue;
used[i] = true;
path.push_back(nums[i]);
dfs(nums, depth+1, size, path, used);
used[i] = false;
path.pop_back();
}
}
}
vector> permuteUnique(vector& nums) {
int size = nums.size();
if (size == 1)
return {nums};
sort(nums.begin(), nums.end());
vector used(size, false);
dfs(nums, 0, size, {}, used);
return res;
}
};
复杂度分析
- 时间复杂度： O ( N ∗ N ! ) O(N*N!) O(N∗N!)
- 空间复杂度： O ( N ) O(N) O(N)
- https://leetcode.cn/problems/permutations-ii/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liwe-2/
