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.

Another way to go about it to use backtracking and using a set to keep track of the elements that have already been used in the current permutation.

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])
  • Alternate Approach

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        buffer = []
        used = set()

        l = len(nums)

        def dfs():
            if len(buffer) == l:
                res.append(buffer.copy())
                return

            for i in range(l):
                if i in used:
                    continue

                buffer.append(nums[i])
                used.add(i)

                dfs()

                used.remove(i)
                buffer.pop()

        dfs()
        return res

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.