-
Notifications
You must be signed in to change notification settings - Fork 0
LC 0046 0047 [M] [M] Permutations I II
Code with Senpai edited this page Jun 20, 2022
·
15 revisions
HAT
cur = nums[i] | prefix + suffix = rest
H + AT
A H + T
T HA +
the rest gets smaller by 1 char at a time until empty
T: O(n!)
I
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def branch(path, nums):
if not nums:
permutations.append(path)
else:
for i, x in enumerate(nums):
prefix, suffix = nums[:i], nums[i+1:]
rest = prefix + suffix
branch(path + [x], rest)
permutations = []
branch([], nums)
return permutations
II
same level seen cache to get rid of duplicates on the same level (a global cache won't work because it will throw out valid permutations across all levels)
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def branch(path, nums):
if not nums:
permutations.append(path)
else:
level_cache = set() # same level
for i in range(len(nums)):
if nums[i] not in level_cache:
level_cache.add(nums[i]) # mark visited
branch(path + [nums[i]], nums[:i] + nums[i+1:])
permutations = []
branch([], nums)
return permutations
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
def dfs(nums, path):
if not nums:
res.append(path)
else:
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]: continue
dfs(nums[:i] + nums[i+1:], path + [nums[i]])
dfs(nums, [])
return res
footer