What Is a Permutation? Orderings from Choose, Explore, Undo

A permutation is one ordering of a set of values. [1, 2] and [2, 1] are different permutations and the same subset. Subsets ignore order. Permutations are the order.

How it works

Keep a path and a used flag for each index. When the path is as long as the input, copy it into the results. The copy matters. If you store the path array itself, a later pop changes every result that pointed at that same array.

Then undo: pop the value and clear the used flag, so the next choice can use it in a different position. Loop the indexes from left to right if the tests want that order. An empty input has one empty permutation.

Ordered picks of length k stop when the path reaches k instead of the full length. The undo is the same. n distinct values have n! full permutations, which is why you only list them when n is small.

ThemeKiln

Terminal

Press Run to execute this example. Use console.log to print a value.

ResetRun

Expected output: [[1, 2], [2, 1]], then [[]]. The empty permutation is one completed ordering with zero choices, not zero orderings.

Worked example

Choose 1, then 2, and save [1, 2]. Undo 2 and then 1. Choose 2, then 1, and save [2, 1]. Every recursive return restores both path and used to the state the caller had.

Why it is correct

At depth d, the path contains d distinct input indexes. The loop tries every index not yet used, so every legal next choice is explored. A path of length n is one complete ordering and is copied exactly once. Any permutation determines one unique sequence of index choices, so all permutations appear and none repeat when the input values are distinct.

Cost

There are n! results, each of length n, so producing the output takes O(n · n!) time and O(n · n!) result space. The active path, flags, and recursion use O(n) auxiliary space. Duplicate input values require an additional skip rule if value-distinct output is desired; this version treats positions as distinct.

In the course

Backtracking lists subsets, where order does not matter and the tests compare a set. The next lesson lists permutations and then ordered picks of length k. The choose, explore, undo rhythm is the same. The choice is different: which unused value comes next, not whether the next value is included.

Common mistakes

Pushing the path without copying, so every saved row changes together.

Forgetting to clear the used flag. Later orderings then skip a value that should have been free.

Sorting each row before you return it. That erases the order the exercise asked for.

When to use it

Use this search when you must list orderings, or ordered selections, and the input is small enough that n! is acceptable.

When not to

Do not list permutations when you only need a count, or when order does not matter. A subset count is 2ⁿ, and listing n! rows is the slower question.

Problem-solving checklist

Define one search state in words: the path plus which indexes are used. Identify the completion condition. Pair every mutation with its undo. Test empty and one-value inputs, then verify that n distinct values produce n! rows without changing the input.

Optional enrichment

Support duplicate input values without returning duplicate permutations. Sort a copy, skip equal unused choices at the same depth, and explain why indexes still need separate used flags.