cf.completefrontend
RECURSION & BACKTRACKING · CORE

Generating permutations

List every order in which a set of items can be arranged by choosing an unused item for each position.

Time O(n! × n)Space O(n)5 practice problemsStep-through picture

The idea

A permutation is one way to put items in order. The items [1, 2, 3] can be ordered 6 ways: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1].

With n items there are n choices for the first spot, n - 1 for the second, and so on. That product is written n! (n factorial). It grows very fast: 5! = 120, 8! = 40,320, and 10! is more than 3 million.

The backtracking way: fill the order from left to right. For each spot, try every item that isn't used yet. A used array of true/false values remembers which items are already in the path. After going deeper, mark the item as free again and try the next one.

An everyday example

Seating guests along a bench

You want to try every seating order for three guests on a bench. You seat someone in the first seat, then someone who is still standing in the second seat, then the last guest. You write the order down. Then the last guest stands up, the second guest stands up, and someone else who is standing takes the second seat. Guests who are seated can't be seated twice, so you check who is still standing.

How the example maps to the code
In the exampleIn the code
The guests on the bench, left to rightThe path array
Who is already seatedused[i] === true
Seating a standing guestused[i] = true; path.push(items[i])
The guest stands up againpath.pop(); used[i] = false
Every seat is filled: write the order downresults.push([...path])

From the slow way to generating permutations

  1. A first idea: fill each of the n spots with any item, which gives n^n lists, and then keep only the lists that use every item once. For 8 items that is 16,777,216 lists to build and check, and only 40,320 of them are real orders. More than 99% of the work is thrown away.
  2. The waste comes from using an item twice. You can see that the moment you pick it: if an item is already in the order, picking it again can never lead to a valid order. So check before you place an item, not after the list is full, and the bad lists are never built.
  3. The check must be fast. Searching path with path.includes(...) costs up to n steps, and it also breaks when two items have the same value. Instead, keep a used array of true/false values, one per index. Checking used[i] takes one step, and two equal values at different indexes stay separate items.
  4. Now fill the order from left to right. At each spot, loop over every index from 0, because any unused item may come next. Skip i when used[i] is true; otherwise mark it, push items[i], go deeper, then pop and unmark it. When path holds every item, save a copy. That loop is generating permutations.

How it works

  1. Keep results, a path for the order being built, and a used array that starts all false.
  2. In explore, if path has as many items as the input, save a copy and return.
  3. Otherwise loop i over every index. Skip i when used[i] is true.
  4. Mark used[i] = true and push items[i] onto path.
  5. Call explore() to fill the next position.
  6. Undo both changes: path.pop() and used[i] = false.
  7. Call explore() once and return results.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function permutations(items) {
  2. const results = [];
  3. const path = [];
  4. const used = new Array(items.length).fill(false);
  5. function explore() {
  6. if (path.length === items.length) {
  7. results.push([...path]);
  8. return;
  9. }
  10. for (let i = 0; i < items.length; i++) {
  11. if (used[i]) continue;
  12. used[i] = true;
  13. path.push(items[i]);
  14. explore();
  15. path.pop();
  16. used[i] = false;
  17. }
  18. }
  19. explore();
  20. return results;
  21. }

How fast it is

TimeO(n! × n)
Extra memoryO(n)

There are n! orders and each copy takes n steps. Apart from the output, path, used, and the call chain each use at most n slots.

  • Best caseO(n! × n)

    Every input of size n. There's no rule to cut branches early, so every order is built and copied: 6 orders for 3 items, 40,320 for 8.

  • Average caseO(n! × n)

    Any input. The values never change how many orders exist.

  • Worst caseO(n! × n)

    Any input. Counting the calls too: 16 calls for 3 items and 109,601 calls for 8 items, still dominated by the n! saved orders times their n items.

Common mistakes

  • Forgetting to reset used[i] = false after the deeper call. The item stays blocked, and later branches miss orders.
  • Starting the loop at a start index as in subsets. That only builds orders that keep the input order, which is just one of them.
  • Removing duplicates at the end with a Set of joined strings. It works, but still builds every duplicate first. Skip equal items during the search instead.
  • Running it on 12 or more items. 12! is about 479 million orders, which will freeze the page.

When to use it

Look for these clues in a problem:

  • The question asks for "every order", "all arrangements", or "all ways to rearrange".
  • Order matters: [1, 2] and [2, 1] count as different answers.
  • The input is tiny, usually 10 items or fewer, because there are n! orders.
  • Each position must be filled with a different item from the input.

Check yourself

Answer each one in your head first, then open it.

How many times is explore called for 3 items?

16 times: 1 call with an empty path, 3 with one item, 6 with two items, and 6 with all three items, which save the orders.

Why does the loop start at 0 instead of at a start index?

In an order, any unused item may come next, even one with a smaller index. Starting at a start index would only build the order that matches the input, as in subsets.

What goes wrong if used is a Set of values instead of an array of indexes, for [4, 4, 9]?

After placing one 4, the value 4 counts as used, so the second 4 can never be placed. path never reaches 3 items, and the result is [].

Why must used[i] = false come after the deeper call, not before it?

During the deeper call, items[i] sits in path, so it must stay blocked. Clearing it early would let the deeper call place the same item twice.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule: when explore is called, path holds different indexes' items, and used[i] is true exactly for the indexes already in path. It starts true, with an empty path and every used[i] set to false. Each loop step marks used[i] and pushes in the same step, and after the deeper call it pops and unmarks, so the rule is back to how it was.

Every order is found. Pick any order of the indexes. At the first spot, the loop reaches that order's first index, which is unused, and places it. At the second spot, the loop starts at 0 and reaches the second index, which is also unused, because only the first is marked. Spot by spot, the search follows that order to the end and saves it.

Each order is found once, and the search ends. Two different orders differ at some first spot, so they come from different loop steps at that depth. The depth never goes past n, and each loop has n steps, so the search is finite. It saves exactly n! orders: n choices for the first spot, n - 1 for the second, and so on.

Going deeper

3 more ideas

Why every order appears exactly once

The first spot tries each item once. For each of those, the second spot tries each remaining item once, and so on. Two different paths through these choices differ at some first spot, so they produce different orders. And any order you can name can be built by choosing its items spot by spot. So each order is produced once.

Repeated items

For [1, 1, 2], swapping the two 1s gives the same order, so a plain search returns duplicates. Sort the items, then skip items[i] when it equals items[i - 1] and used[i - 1] is false. That rule makes equal items always appear in their original order, so each distinct order is built once.

The cost

There are n! orders, each copied in n steps, so the time is O(n! × n). Even n = 11 gives about 40 million orders, so permutation search only works on tiny inputs. If a problem only needs one specific order, such as the next one in sorted order, there is usually a direct method that avoids listing them all.

Work it by hand

Every step in a table, with why

List every order of 3 numbers. Each row is one item being placed. In the used column, T means true and F means false.

items = [5, 8, 2]

Stepipath after the pushusedWhat happensWhy
10[5][T, F, F]first spot gets 5The top-level loop starts at i = 0. Nothing is used yet, so 5 takes the first spot.
21[5, 8][T, T, F]second spot gets 8The deeper loop starts at 0 again, but used[0] is true, so it skips to i = 1.
32[5, 8, 2][T, T, T]save [5, 8, 2]Only i = 2 is free. path now holds 3 items, so the next call saves a copy and returns.
42[5, 2][T, F, T]second spot gets 2Undo 2 and 8. The second-spot loop moves on to i = 2, so 2 now comes second.
51[5, 2, 8][T, T, T]save [5, 2, 8]8 is free again because its used mark was cleared, so it fills the last spot.
61[8][F, T, F]first spot gets 8Every order starting with 5 is done. used[0] is cleared, and the top loop moves to i = 1.
70[8, 5][T, T, F]second spot gets 5The deeper loop starts at 0 again, and 5 is free now.
82[8, 5, 2][T, T, T]save [8, 5, 2]A full order: save it.
92[8, 2][F, T, T]second spot gets 2Undo, and try the last free item in the second spot.
100[8, 2, 5][T, T, T]save [8, 2, 5]5 is the only free item left, so it fills the last spot.
112[2][F, F, T]first spot gets 2The top loop reaches its last index, i = 2.
120[2, 5][T, F, T]second spot gets 5used[2] is true, so only 5 and 8 are free.
131[2, 5, 8][T, T, T]save [2, 5, 8]A full order: save it.
141[2, 8][F, T, T]second spot gets 8Undo, and put 8 second instead.
150[2, 8, 5][T, T, T]save [2, 8, 5]The last order. Every loop then runs out of indexes, and the first call returns.

It returns [[5, 8, 2], [5, 2, 8], [8, 5, 2], [8, 2, 5], [2, 5, 8], [2, 8, 5]]: all 3! = 6 orders, after 15 placements. The orders follow index order, so they would come out sorted if items were sorted.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Generating permutationsO(n · n!)O(n)You need every order, in sorted order, with an easy place to add skip rules for repeats or other limits.
Swap in placeO(n · n!)O(n)Memory is tight and the output order doesn't matter, since it avoids the path and used arrays.
Next permutation loopO(n · n!)O(1)You want orders one at a time, in sorted order, without recursion, or only the next order after a given one.

Extra memory: O(n) besides the output: path, used, and the call chain each hold at most n entries. The output holds n! × n numbers.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Generating permutations and the other approaches, on a scale where each line up is 10 times more steps.
  • Generating permutations O(n · n!)
  • Swap in place O(n · n!)
  • Next permutation loop O(n · n!)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Generating permutations36 millionmore than a quadrillionmore than a quadrillion
Swap in place36 millionmore than a quadrillionmore than a quadrillion
Next permutation loop36 millionmore than a quadrillionmore than a quadrillion

Inputs that need care

5 tricky inputs
An empty list: items = []
path.length === items.length is true at once, so it saves [] and returns [[]]. There is exactly one way to order nothing.
One item: items = [7]
One placement, one save: [[7]].
Repeated values: items = [4, 4, 9]
The code returns 6 orders, but only 3 are different: [4, 4, 9], [4, 9, 4], and [9, 4, 4] each appear twice. Sort, then skip items[i] when it equals items[i - 1] and used[i - 1] is false. That gives exactly the 3 different orders.
Ten or eleven items
10! is 3,628,800 orders and 11! is 39,916,800. The code is correct but can freeze a page. Ask whether you need the orders themselves, or only one specific order or a count.
A string such as "abc"
Pass [..."abc"] as items and turn each saved order back into text with join(""). The algorithm itself only sees a list.

Variations and follow-ups

Twists interviewers add

Swap in place

Instead of path and used, swap items[pos] with each items[i] where i >= pos, recurse on pos + 1, then swap back. The part of the array before pos is the order so far. It needs no extra arrays, but the orders don't come out sorted: for [5, 8, 2] the last two are [2, 8, 5] and [2, 5, 8].

Next permutation

From the current order, find the rightmost i with a[i] < a[i + 1], swap a[i] with the rightmost larger item after it, and reverse everything after i. Starting from the sorted order and repeating lists every order in sorted order, with no recursion and no used array. Repeated values are handled for free.

Orders of only k items

Save when path.length === k instead of when it holds every item. This lists the n! / (n - k)! ways to fill k ordered spots, such as first, second, and third place in a race.

Orders without repeats

With the sort-and-skip rule, equal values are always placed in their original left-to-right order. So each different order is built exactly once, instead of being built many times and removed at the end.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "all arrangements", "every order", or "all ways to rearrange", where [1, 2] and [2, 1] count as different, and the input has about 8 items or fewer.
  • Explain why the loop starts at 0 and not at a start index: any unused item can fill the next spot. Then explain that used is indexed by position, so equal values are still separate items.
  • Test [], one item, and a list with two equal values. The last one shows whether you thought about repeats before the interviewer asks.
  • The usual follow-up is "what if there are repeated values?". Answer: sort, then skip items[i] when it equals items[i - 1] and used[i - 1] is false. Explain that this forces equal values to be used left to right.
  • Another follow-up is "find the k-th order without listing them". Each choice for the first spot covers (n - 1)! orders, so divide k by (n - 1)! to pick the first item, then repeat on the rest.

Where frontend code uses it

The same idea in real UI code
  • Race-condition tests sometimes fire a few async responses in every possible order to check that the UI ends in the right state each time.
  • Drag-and-drop reordering in a list or a tab bar produces one permutation of the items. Tests that check all orders of three or four items list the permutations.
  • When a tool tries every order of a few steps, such as every order of applying middleware or CSS classes, to see which one gives the wanted result, it is searching permutations.

Related algorithms