Permutations

Tags

Permutations

Category

Recursion

Difficulty

Medium

Problem Statement

Given an array of unique integers, return all possible permutations of the array. Each permutation must contain every element exactly once, and the order of permutations in the output does not matter.

Intuition

A permutation is an ordered arrangement of all elements. To build permutations, we can think of it as making a choice at each position: for the first position, we can pick any of the n elements; for the second, any of the remaining n-1; and so on. This naturally leads to a recursive backtracking approach where we swap elements into the current position and recurse on the rest.

Approach

  1. Use a recursive function that takes the array and a starting index.
  2. If the starting index equals the length of the array, we have a complete permutation — add a copy of the array to the results.
  3. Otherwise, for each index i from start to the end of the array:
    • Swap the element at start with the element at i.
    • Recurse with start + 1.
    • Swap back (backtrack) to restore the original order.

An alternative approach builds permutations by maintaining a "remaining" list and a "current permutation" list, choosing one element at a time from "remaining" and adding it to "current."

Pseudocode

function permutations(array):
    results = []
    helper(array, 0, results)
    return results

function helper(array, start, results):
    if start == length(array):
        results.append(copy(array))
        return
    for i from start to length(array) - 1:
        swap(array[start], array[i])
        helper(array, start + 1, results)
        swap(array[start], array[i])

Time & Space Complexity

  • Time: O(n * n!) — there are n! permutations and creating each one takes O(n) work (copying the array).
  • Space: O(n * n!) — to store all n! permutations, each of length n. The recursion call stack adds O(n) depth.

Key Insights

  • Backtracking is essential: after exploring all permutations with a particular element at position start, we swap it back so the next iteration can try a different element.
  • The swap-based approach modifies the array in place, which is more space-efficient during computation than creating new sub-arrays.
  • The number of permutations grows factorially, so this problem is inherently expensive for large inputs.
  • Every element must appear in every position across the full set of permutations.

Edge Cases

  • Empty array [] should return [[]] (one permutation: the empty permutation).
  • Single-element array [1] returns [[1]].
  • Array with two elements [1, 2] returns [[1, 2], [2, 1]].
  • All elements are guaranteed unique, so no deduplication is needed. If duplicates were present, additional logic would be required to skip redundant swaps.

Linked mentions