V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Permutations

Choose one unused value per depth, record complete arrangements, and undo choices while exploring the decision tree.

Core idea

Fill one output position at a time by choosing any unused input value. A boolean used set enforces uniqueness, and backtracking releases each value for sibling branches.

Read the visualization

The decision tree has one level per output position. Descending edges add a value, leaf nodes record complete arrangements, and returning upward removes the final choice.

select 1select 2select 3select 3select 2select 2select 1select 3select 3select 1select 3select 1select 2select 2select 1[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]

Start at the empty arrangement with every input value available.

1function permute(nums: number[]): number[][] {
2 const res: number[][] = [];
3 const cur: number[] = [];
4 const used = new Array(nums.length).fill(false);
5 const backtrack = (): void => {
6 if (cur.length === nums.length) {
7 res.push([...cur]);
8 return;
9 }
10 for (let i = 0; i < nums.length; i++) {
11 if (used[i]) continue; // skip already choose(choose)
12 used[i] = true;
13 cur.push(nums[i]); // select nums[i]
14 backtrack();
15 cur.pop(); // backtrack( backtrack)
16 used[i] = false;
17 }
18 };
19 backtrack();
20 return res;
21}
element1 2 3
current permutation[]
remaining{1,2,3}
collected0 / 6
1 / 28

Complexity and tradeoffs

Time: O(n × n!). Space: O(n). There are n! outputs, and writing each arrangement requires O(n) work.

Invariant: The current path contains distinct values and is exactly the prefix shared by every permutation in its subtree.

Where it fits

Permutation search appears in small assignment, ordering, and route problems. Duplicate input values require sorting plus a same-depth skip rule to avoid repeated outputs.