MediumArrayBacktrackingUpdated Sep 2026

46. Permutations

Asked at Oracle

Difficulty

Medium

Time

O(n * n!)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given an array nums of distinct integers. Return every possible ordering of all the elements — that is, all permutations of the array.

A permutation must use each element exactly once. Since the values are all different, no two orderings will look the same. The order in which you list the permutations in your answer does not matter.

The number of permutations is n!, where n is the length of nums. For example, [1,2,3] has 3! = 6 permutations.

Every ordering of all elements

nums123012The input has 3 distinct values, so 3! = 6 answers areexpected.answers012123456123132213231312321Each row is one valid permutation; the order of therows does not matter.
For [1,2,3] we must list all 6 orderings, each using 1, 2 and 3 exactly once.

Constraints

  • ●1 <= nums.length <= 6
  • ●-10 <= nums[i] <= 10
  • ●All the integers of nums are unique.

Examples

Example 1
Inputnums = [1,2,3]
Output[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
WhyThere are 3! = 6 orderings. Fixing 1 first, the rest can be [2,3] or [3,2]; the same holds when 2 or 3 comes first, giving all six.
Example 2
Inputnums = [0,1]
Output[[0,1],[1,0]]
WhyWith two elements there are 2! = 2 orderings: 0 then 1, or 1 then 0.
Example 3
Inputnums = [1]
Output[[1]]
WhyA single element has only one ordering, which is the element itself.

Asked At

1 companies
CompanyDifficulty
OracleMediumView all Oracle questions →

How to Think About It

1

Brute force: generate all possible orderings and check if they use every element exactly once.

2

Backtracking: fix one element at a position and recurse on the remaining elements.

3

Swap-based backtracking: swap each remaining element into the current position, recurse, then swap back (backtrack).

4

Permutation via visited array: maintain a boolean visited array and build each permutation by choosing unvisited elements.

5

Optimal: O(n * n!) time using swap-based in-place backtracking with no extra space for the permutation itself.

Optimal Approach

Use backtracking to build permutations element by element. At each recursive level, iterate through the remaining unvisited elements, place the element at the current position, recurse to fill the next position, then undo the placement (backtrack). A visited boolean array tracks which elements are already used. The base case is when the current permutation length equals the input length, at which point a copy of the permutation is added to the result. This produces all n! permutations in O(n * n!) time and O(n) space for the recursion stack.

Backtracking: choose, recurse, undo

path10Pick 1 for position 0, then recurse to fill theremaining positions.path123012Path length equals n, so [1,2,3] is a completepermutation — save a copy.path1301Undo the 2 (pop it), then try 3 instead to explore theother branch.if len(path) == n: save copyfor each unused i: use it, recurse, undon! leaves in the recursion tree
We build the permutation one position at a time, trying each unused element, then undo the choice to try the next one.
ComplexityTime O(n * n!)Space O(n)There are n! permutations and copying each one costs O(n); the extra space is just the recursion stack and the used array, both of size n.

What Trips People Up in Real Interviews

1

Clarify whether the input contains duplicates — this problem assumes distinct integers.

2

Mention the factorial time complexity upfront so the interviewer knows you understand the growth.

3

Walk through a small example (e.g., [1,2,3]) step by step before coding.

4

Explain the backtracking template: choose, explore, un-choose.

5

Discuss the difference between swap-based and visited-array approaches and trade-offs in space.

Solution Code

O(n * n!) time
def permute(nums):
    result = []
    n = len(nums)
    used = [False] * n
    def backtrack(path):
        if len(path) == n:
            result.append(path[:])
            return
        for i in range(n):
            if not used[i]:
                used[i] = True
                path.append(nums[i])
                backtrack(path)
                path.pop()
                used[i] = False
    backtrack([])
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Permutations problem?

Given an array of distinct integers nums, return all possible permutations of the array. You may return the answer in any order. The total number of permutations is n! where n is the length of the input array.

How do you solve Permutations?

The optimal approach runs in O(n * n!) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Permutations?

Permutations is asked at Oracle. It is a medium difficulty problem.

What are common mistakes on Permutations?
  • Clarify whether the input contains duplicates — this problem assumes distinct integers.
  • Mention the factorial time complexity upfront so the interviewer knows you understand the growth.
  • Walk through a small example (e.g., [1,2,3]) step by step before coding.
  • Explain the backtracking template: choose, explore, un-choose.
  • Discuss the difference between swap-based and visited-array approaches and trade-offs in space.