Permutations
Asked at Oracle
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Oracle | MEDIUM | View all Oracle questions → |
How to Think About It
Brute force: generate all possible orderings and check if they use every element exactly once.
Backtracking: fix one element at a position and recurse on the remaining elements.
Swap-based backtracking: swap each remaining element into the current position, recurse, then swap back (backtrack).
Permutation via visited array: maintain a boolean visited array and build each permutation by choosing unvisited elements.
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.
What Trips People Up in Real Interviews
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.
Solution Code
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 resultFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.