class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
}
};
剑指 Offer II 084. 含有重复元素集合的全排列
给定一个可包含重复数字的整数集合 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/
原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 3.6 MB, 提交时间: 2022-11-20 17:25:30
func permuteUnique(nums []int) (ans [][]int) {
sort.Ints(nums)
n := len(nums)
perm := []int{}
vis := make([]bool, n)
var backtrack func(int)
backtrack = func(idx int) {
if idx == n {
ans = append(ans, append([]int(nil), perm...))
return
}
for i, v := range nums {
if vis[i] || i > 0 && !vis[i-1] && v == nums[i-1] {
continue
}
perm = append(perm, v)
vis[i] = true
backtrack(idx + 1)
vis[i] = false
perm = perm[:len(perm)-1]
}
}
backtrack(0)
return
}
php 解法, 执行用时: 12 ms, 内存消耗: 19.1 MB, 提交时间: 2022-11-20 17:24:49
class Solution {
/**
* @param Integer[] $nums
* @return Integer[][]
*/
function permuteUnique($nums) {
sort($nums);
$res = [];
$this->__backtrack($nums, [], $res);
return $res;
}
function __backtrack(array $nums, array $temp=[], array &$res=[])
{
if ( empty($nums) ) {
$res[] = $temp;
return;
} else {
for ( $i = 0; $i < count($nums); $i++ ) {
if ( $i > 0 && $nums[$i] == $nums[$i-1] ) continue;
$this->__backtrack(array_merge(array_slice($nums, 0, $i), array_slice($nums, $i+1)), array_merge($temp, [$nums[$i]]), $res);
}
}
}
}
python3 解法, 执行用时: 692 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-20 17:24:29
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
ans = []
for k in itertools.permutations(nums):
if list(k) not in ans:
ans.append(list(k))
return ans