Permutations

Medium#46permutations

You get a list of different numbers. Return every order they can stand in, each once, in any order. Our example: [4, 5, 6] has 3! = 6 orders, from [4, 5, 6] to [6, 5, 4].

46 PermutationsWalkthrough · 1×

Example: every order of [4, 5, 6], made by swaps in the list itself. Watch the root: after each branch the second swap puts the list back to [4, 5, 6], and swapping 4 with 6 gives [6, 5, 4] before [6, 4, 5].

[ ]44,54,5,64,64,6,555,45,4,65,65,6,466,56,5,46,46,4,5nums041526results—
not reached yet; position still freeon the way here; position fixedthis step; the two numbers swappedsaved orderfinished

Find every order of [4, 5, 6]

01/57
restart · back · play · step
Speed
1function permute(nums):
2 results = []
3 arrange(0)
4 return results
5
6function arrange(start):
7 if start == len(nums):
8 add copy of nums to results
9 return
10 for i from start to len(nums) - 1:
11 swap nums[start], nums[i] // nums[i] to start
12 arrange(start + 1)
13 swap nums[start], nums[i] // undo
state
start
–
i
–
nums
[4, 5, 6]
results
–
click a step to go back

← → step · space play/pause

Why it works

  1. The part before start is fixed; swapping each of nums[start..] into position start tries every number still free there, once each, so every order is built exactly once.
  2. The second swap undoes the first: when a call comes back, the list is exactly as it was, so the next i swaps from the same order and no number is lost or repeated.
  3. When start reaches the end, every position is fixed and the list itself is one order: a copy of it is saved.

Complexity

Time O(n × n!): n! orders, each copied in n steps; the calls above the leaves add fewer than that again. Memory O(n) besides the answer: the swaps work in the list itself, and the call stack is n deep.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.