Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Permutations

LeetCode #46Medium
Choose an unused element at each level

Given an array of distinct integers, return all possible orderings (permutations) of the array, in any order.

Asked atAmazonGoogleMeta
step 1 / 33
solution-space tree
[1,2,3]
[1,2]
[1,3,2]
[1,3]
[1]
[2,1,3]
[2,1]
[2,3,1]
[2,3]
[2]
[3,1,2]
[3,1]
[3,2,1]
[3,2]
[3]
[ ]
permutations
(none yet)
Backtracking · choose an unused element at each level
▸
1permute(path, used):
2    if path.length == n:
3        record path             // a complete permutation
4    for num in nums where !used[num]:
5        used[num] = true; path.push(num)   // choose
6        permute(path, used)                // explore
7        used[num] = false; path.pop()      // un-choose (backtrack)
state
  • input[1, 2, 3]

line 1Generate EVERY ordering of [1, 2, 3]. At each level we CHOOSE one number that has not been used yet, then recurse on what is left. A path from the root to a depth-3 leaf spells out one full permutation.