Skip to main content

Permutations

Question​

com

What is the most efficient algorithm for generating all permutations of a given array in LeetCode?

Example 1
Input: [1,2,3]

Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Solution​

all//Permutations.py


def permutations(arr):

  # Base case: If the array is empty, return an empty list
  if len(arr) == 0:
    return []

  # If the array only contains one item, return a list with that item
  if len(arr) == 1:
    return [arr]

  # Define the result list
  result = []

  # Iterate over the array
  for i in range(len(arr)):
    # Pop the first item from the array
    curr = arr.pop(i)
    # Recursively call the function on the remaining array
    for p in permutations(arr):
      # Append the current item to each permutation
      result.append([curr] + p)
    # Put the item back in the array
    arr.insert(i, curr)

  return result