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