< Back




46. Permutations

We're given a list of integers, nums, and asked to provide all possible permutations. A permutation
is a rearrangement of the elements provided in the original list. We're asked to provide a list of
these permutations with no duplicate results.

To solve this, we use a technique known as backtracking. We treat each element in the original list,
nums, as a node in a graph. When we visit each node, the child nodes will be the other numbers in
the original list that aren't the current nodes. We continue to traverse the graph until the
current node's length is equal to the length of the original list.

What we're doing at each node is adding numbers to the permutation candidate. When we travel to the
child node, if the permutation candidate is complete, we add it to the answer list, and then return.
Otherwise, we continue to travel to child nodes. After a child node completes its backtracking
procedure, we pop the number we added to the list off, and visit the next child.

Because of the terrible time complexity of this algorithm, we maintain a hash set that we can use to
conduct O(1) time lookups - this allows us to tell when a number is / isn't in the permutation
candidate faster than a list.

The solution is as follows:


  class Solution:
      def permute(self, nums: List[int]) -> List[List[int]]:
          ans, n = [], len(nums)

          def backtrack(curr: List[int], curr_set: set) -> None:
              if len(curr) == n:
                  ans.append(curr[:])
                  return

              for num in nums:
                  if num not in curr_set:
                      curr.append(num)
                      curr_set.add(num)
                      backtrack(curr, curr_set)
                      curr.pop()
                      curr_set.discard(num)

          backtrack([], set())
          return ans


_ Time Complexity:

  O(n * n!) - Where n is the length of nums.

_ Space Complexity:

  O(n) - The size of the permutation candidates we maintain are at most the length of nums.