Topic · BacktrackingMedium
Permutations
Understand the problem
Given an array of distinct integers nums. Return all possible permutations — each element appears exactly once in each permutation.
Examples:
ts
nums = [1, 2, 3]
output = [
[1,2,3], [1,3,2],
[2,1,3], [2,3,1],
[3,1,2], [3,2,1]
]
// n! = 3! = 6 permutations
nums = [0, 1]
output = [[0,1], [1,0]]Unlike subsets: each element is used exactly once and order matters (a permutation differs from a combination).
Use a used array to track which elements are already in the current permutation.
Basic approach
O(n × n!) time — n! permutations, each takes O(n) to copyts
// Naive approach: generate every length-n sequence, then filter — O(n × n!) plus overhead
// Impractical in practice; backtracking is the efficient way
// Demo: permute by swapping positions (in-place swap)
function permuteSwap(nums: number[]): number[][] {
const result: number[][] = []
function backtrack(start: number) {
if (start === nums.length) {
result.push([...nums])
return
}
for (let i = start; i < nums.length; i++) {
;[nums[start], nums[i]] = [nums[i], nums[start]] // swap
backtrack(start + 1)
;[nums[start], nums[i]] = [nums[i], nums[start]] // swap back
}
}
backtrack(0)
return result
}Why this approach is slow:
The swap version also reaches O(n×n!) but modifies the original array (in place).
The version with a separate used array is cleaner and does not modify the input — a better fit when the problem forbids modifying the input.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.