Problem Statement in English

You’re given an array of distinct integers nums. Return all the possible permutations. You can return the answer in any order.

It is guaranteed that each number in nums is unique.

Approach

We can solve this problem using a recursive approach where we swap elements to generate all possible permutations. The idea is to fix one element at a time and recursively generate permutations for the remaining elements.

So think of it in terms of levels in a tree. At each level, we swap the current element with each of the elements that come after it (including itself) to generate new permutations.

Solution in Python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def swap(level, arr):
            l = len(arr[0])

            if level == l-1:
                return arr

            res = []

            for carr in arr:
                temp = carr[level]

                for i in range(level, l):
                    buffer = carr.copy()
                    buffer[level] = buffer[i]
                    buffer[i]=temp

                    res.append(buffer)

            return swap(level+1, res)

        return swap(0, [nums])

Complexity

  • Time: $O(n \times n!)$
    Since there are n! permutations and generating each permutation takes O(n) time.

  • Space: $O(n \times n!)$
    The space complexity is O(n × n!) to store all the permutations.

And we are done.