LC 0046 0047 [M] [M] Permutations I II - ALawliet/algorithms GitHub Wiki

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