DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Permutations

mediumRecursion Must-do

Problem statement

Given an array of distinct integers, return every ordering (permutation) of its values. Each permutation uses every value exactly once. The permutations can be returned in any order.

An array of n distinct values has n! permutations.

Examples

Example 1

Input: nums = [3, 8]

Output: [[3, 8], [8, 3]]

Example 2

Input: nums = [1, 2, 3]

Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Explanation: 3! = 6 orderings.

Hints

Approach

Only ever extend the current ordering with a value that has not been used yet. A boolean array used makes that check O(1).

  1. dfs(): if path has n values, record a copy.
  2. Otherwise, for each index i with used[i] false: mark it used, append nums[i], recurse.
  3. After the call returns, pop the value and clear used[i] so the next branch can use it.

Every leaf of this recursion is a real permutation, so no work is wasted on invalid sequences. There are n! leaves and copying each one costs O(n), which matches the size of the output.

ComplexityTime O(n · n!)Space O(n) for `path`, `used` and the recursion, besides the output
Python
class Solution:
def permute(self, nums: list[int]) -> list[list[int]]:
result, path = [], []
used = [False] * len(nums)
def dfs() -> None:
if len(path) == len(nums):
result.append(path[:])
return
for i, v in enumerate(nums):
if used[i]:
continue
used[i] = True
path.append(v)
dfs()
path.pop() # undo the choice
used[i] = False
dfs()
return result

Follow-up questions

  • The input may contain duplicate values. Return only distinct permutations.
  • Return only the k-th permutation in sorted order without generating the others.

Frequently asked questions

Yes. Permute in place by swapping: at depth d, swap nums[d] with each nums[i] for i >= d, recurse on d + 1, then swap back. It has the same complexity and saves the boolean array, but the output order is less predictable.

Sort first. In the loop, skip nums[i] when it equals nums[i - 1] and nums[i - 1] is not currently used. That way equal values are always placed in a fixed relative order, and each distinct permutation appears once.

Trying every order of steps, such as the order in which to drain nodes or apply migrations, is a permutation search. Knowing it grows as n! is just as important: it tells you when brute-forcing orderings is feasible (a handful of items) and when you need a smarter rule.