Given a list of numbers, return all possible permutations.
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
Given a list of numbers with duplicate number in it. Find all unique permutations.
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