Permutations—LeetCode

Key takeaways:

  • Permutation is an arrangement of a set’s elements in a specific order. It’s reordering the elements in a set to create different sequences.

  • Permutations are a fundamental concept in mathematics with applications in various fields due to their ability to model and analyze problems involving order and arrangement. They are essential for counting and probability, discrete mathematics and algorithms, and cryptography.

  • The time complexity of generating all permutations is O(n!), and the space complexity is O(n * n!). These complexities arise due to the factorial growth in the number of permutations as the input size increases.

A permutation is an arrangement of a set’s elements in a specific order. For a given set of distinct elements, a permutation involves reorganizing those elements into different sequences where the order of the elements matters. For example, for the set, {1, 2, 3}, the possible permutations are {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, and {3, 2, 1}. Each unique sequence is a permutation of the original set.

Permutations are a fundamental concept in mathematics with applications in various fields due to their ability to model and analyze problems involving order and arrangement. They are essential for tasks such as:

  • Counting and probability: Calculating the number of ways to arrange objects or elements, and determining probabilities in situations where order matters.

  • Discrete mathematics and algorithms: Studying graph theory, designing algorithms, and solving combinatorial problems.

  • Cryptography: Encrypting and decrypting data, designing ciphers, and ensuring data security.

Problem statement

In the LeetCode problem, given an array, nums, of distinct integers, return all possible permutations. The order of the permutations does not matter.

Constraints:

  • 1 <= nums.length <= 6

  • -10 <= nums[i] <= 10

  • All the integers of nums are unique.

Example 1:

In this example, the array [4,5,6] can be rearranged in six ways.

Input: nums = [4,5,6]
Output: [[4,5,6],[4,6,5],[5,4,6],[5,6,4],[6,4,5],[6,5,4]]

Example 2:

Here, the array [7,8] can be rearranged in two ways.

Input: nums = [7,8]
Output: [[7,8],[8,7]]

Example 3:

There is only one possible permutation for a single-element array [9].

Input: nums = [9]
Output: [[9]]

Knowledge test

Attempt the quiz below to test your concepts on the LeetCode permutation problem:

1

What is the result of buildTree([1, 2, 3])

A)

[[1,2,3],[1,3,2],[3,1,2],[3,2,1]]

B)

[[1,2,3],[1,3,2],[2,1,3],[2,3,1]]

C)

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Question 1 of 30 attempted

Algorithm to find the permutations

We can construct an N-array tree, that accumulates the combinations in an accumulator combos when a leaf node is encountered. As we move down the tree, at each step we choose one item from the list combo and recursively build the tree in a depth-first search (DFS) manner. This will be our algorithm for cracking this problem

Lets dry run the problem for Example 1.

We start off with an empty node.
We start off with an empty node.
1 of 4

The following permutations are therefore possible (from left to right in the tree):

  • 123

  • 132

  • 213

  • 231

  • 312

  • 321

Code to find the permutations

Let’s write down the code for this solution.

global combos
combos = []
def buildTree(available:set, combo:list):
    if len(available)==0:
        combos.append(combo.copy())
    else:
        for chosen in available:
            residual = available - set([chosen])
            combo.append(chosen)
            buildTree(residual, combo)
            combo.pop(-1)
nums = [1, 2, 3]
buildTree(set(nums), [])
print("The following permutations are possible:\n", combos)
Code example of the algorithm in Python

Code explanation

  • Lines 1–2: We create and initialize the global variable, combos, that will accumulate the permutations in a list.

  • Lines 4–12: We write the recursive code for gathering the permutations of any given list.

    • Lines 5–6: This is the termination criteria for recursion. When all the items have be used, the code will append the combination combo to the combos accumulator.

    • Lines 7–12: While the termination criteria has not been met, we use a for loop to loop over the available items, and at each step, we remove the chosen item from the available items, append the chosen item to the current combination combo , and recursively run the function with the residual items.

  • Line 14: We declare the nums list that contains the items that we want a permutation for.

  • Line 15: We run the code for finding permutations of the nums array.

  • Line 16: We print the available permutations.

Time complexity

The function buildTree generates all permutations of the input list nums. To understand the time complexity, consider the following points:

  1. Total permutations: For a list of length n, there are n! (or n-factorial) possible permutations.
  2. Recursive calls: The function makes recursive calls; each call iterates over the elements in the available set. In the worst case, this means iterating over n elements at the first level, n-1 elements at the second level, and so on, down to 1 element.

Each recursion level involves iterating through a set of decreasing size, leading to a total number of operations proportional to n * (n-1) * (n-2) * ... * 1 = n!.

Thus, the time complexity of generating all permutations is O(n!).

Space complexity

The space complexity involves the call stack and the space required to store the permutations.

  1. Call stack: The maximum depth of the recursion is n, where n is the length of the input list nums. Each recursion level uses a constant amount of space, so the call stack space complexity is O(n).
  2. Storage for permutations: The combos list stores all permutations. As there are n! permutations, and each is a list of length n, the space required to store all permutations is O(n * n!).

Combining these, the overall space complexity is dominated by the storage for permutations, which is O(n * n!).

Summary

  • Time complexity: O(n!)
  • Space complexity: O(n * n!)

These complexities arise due to the factorial growth in the number of permutations as the input size increases.

Frequently asked questions

Haven’t found what you were looking for? Contact Us

What is permutation in coding?

In coding, a permutation refers to an arrangement of elements in a specific order. It’s a way to rearrange or resequence elements without changing them. For example, given the list [1, 2, 3], permutations could include [1, 2, 3], [2, 1, 3], [3, 2, 1], and so on.

How can you solve permutation problems in coding?

There are several common approaches to solving permutation problems in coding:

  • Backtracking: This method involves exploring all possible paths and backtracking when a dead end is reached. It’s often used for generating all permutations.
  • Recursion: Recursion can be a powerful tool for breaking down a permutation problem into smaller, similar subproblems.
  • Iterative approaches: Some permutation problems can be solved iteratively using algorithms like Heap’s algorithm.

How can you compute a permutation?

The number of permutations of a set of n elements is given by n factorial (n!).

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved