Friedrich Ewald My Personal Website

Leetcode: Permutations

The goal of this task is to find all possible permutations of numbers in a list. For example, [1,2,3] can become [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. Mathematically, the number of possible permutations without using duplicates is n! where n is the number of unique elements in the list. This problem can best be solved by using backtracing and recursion. The general idea is to put all possible digits in the beginning and then cut off the rest of the list and repeat the first step. Later, the list is assembled. The algorithm stops if there is only one item in the list because the only possible permutation is with itself. The other special case that needs to be handled is the empty list which must return the empty list itself.

class Solution:
  def permute(self, nums: List[int]) -> List[List[int]]:
    # There are len(nums)! possible permutations

    res = []
    res += self.inner(nums)
    return res

  def inner(self, nums):
    if len(nums) == 0:
      return []
    
    if len(nums) == 1:
      return [nums]

    res = []

    for i in range(len(nums)):
      # Copy the list to avoid changing it in memory
      t = nums.copy()

      # Swap i-th element with the first, placing every item
      # at the front, one at a time
      t[0], t[i] = t[i], t[0]
      
      # The inner function will return a list of lists.
      # Iterate over all lists and add them to the first 
      # element.
      for perm in self.inner(t[1:]):
        res.append([t[0]] + perm)
    
    return res
      
if __name__ == '__main__':
  r = Solution().permute
  print(r([1,2,3]), [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]])
Runtime: 52 ms, faster than 73.88% of Python3 online submissions for Permutations. Memory Usage: 14.1 MB, less than 22.42% of Python3 online submissions for Permutations.


About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.