const helper = function(nums, level, res) {
if (level === nums.length) {
res.push([...nums])
return
}
const map = new Map()
for (let i = level; i < nums.length; i++) {
if (!map.get(nums[i])) {
map.set(nums[i], true);
[nums[i], nums[level]] = [nums[level], nums[i]]
helper(nums, level + 1, res);
[nums[i], nums[level]] = [nums[level], nums[
i]]
}
}
}
var permuteUnique = function(nums) {
if (nums.length === 0) {
return []
} else if (nums.length === 1) {
return [
[nums[0]]
]
}
nums.sort((a, b) => a - b)
const res = []
helper(nums, 0, res)
return res
};
Runtime: 72 ms, faster than 86.35% of JavaScript online submissions for Permutations II.
Memory Usage: 37.8 MB, less than 22.22% of JavaScript online submissions for Permutations II.
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
if len(nums) == 0:
return []
nums.sort()
used = [False]*len(nums)
res = []
Solution._dfs(self, nums, 0, [], used, res)
return res
def _dfs(self, nums, index, pre, used, res):
if index == len(nums):
res.append(pre.copy())
return
for i in range(len(nums)):
if not used[i]:
if i > 0 and nums[i-1] == nums[i]and not used[i-1]:
continue
used[i] = True
pre.append(nums[i])
Solution._dfs(self, nums, index+1, pre, used, res)
pre.pop()
used[i] = False
Runtime: 56 ms, faster than 97.36% of Python3 online submissions for Permutations II.
Memory Usage: 12.7 MB, less than 100.00% of Python3 online submissions for Permutations II.
把函数放在里面，就可以少传一些参数了。
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
if len(nums) == 0:
return []
nums.sort()
res = []
def _dfs(nums, pre):
if not nums:
res.append(pre)
return
for i in range(len(nums)):
if i > 0 and nums[i-1] == nums[i]:
continue
_dfs(nums[:i]+nums[i+1:], pre+[nums[i]])
_dfs(nums, [])
return res
Runtime: 56 ms, faster than 97.36% of Python3 online submissions for Permutations II.
Memory Usage: 13.1 MB, less than 95.56% of Python3 online submissions for Permutations II.
func permuteUnique(nums []int) [][]int {
if len(nums) == 0 {
return nil
}
sort.Ints(nums)
ans := make([][]int, 0)
dfs(nums, nil, &ans)
return ans
}
func dfs(nums []int, prev []int, ans *[][]int) {
if len(nums) == 0 {
*ans = append(*ans, append([]int{}, prev...))
return
}
for i := 0; i < len(nums); i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
dfs(append(append([]int{}, nums[:i]...), nums[i+1:]...), append(prev, nums[i]), ans)
}
}
Runtime: 8 ms, faster than 95.61% of Go online submissions for Permutations II.
Memory Usage: 7.9 MB, less than 50.00% of Go online submissions for Permutations II.