Permutation
46 Permutation I
Given a list of numbers, return all possible permutations.
A boolean array to record if used
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
visit = [False] * len(nums)
self.backtrack([], nums, visit, res)
return res
def backtrack(self, cand, nums, visit, res):
if len(cand) == len(nums):
res.append(cand.copy())
return
for i in range(len(nums)):
if visit[i]: continue
visit[i] = True
self.backtrack(cand + [nums[i]], nums, visit, res)
visit[i] = False
47 Permutation II
Given a list of numbers with duplicate number in it. Find all unique permutations.
Only traverse the first of duplicate number
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = []
visit = [False] * len(nums)
nums.sort()
self.backtrack([], nums, visit, res)
return res
def backtrack(self, cand, nums, visit, res):
if len(cand) == len(nums):
res.append(cand.copy())
return
for i in range(len(nums)):
if visit[i] or (i>0 and nums[i-1] == nums[i] and visit[i-1] == False): continue
visit[i] = True
self.backtrack(cand + [nums[i]], nums, visit, res)
visit[i] = False
Last updated
Was this helpful?