Given an array of distinct numbers, return all possible orderings. For n numbers there are n factorial permutations.
DSA Animator › DSA Revision › Backtracking › Permutations
Remember: permutations use a used array instead of a start index. Every unused number can go in the next position. The video solves Permutations (LeetCode 46, Medium) with the Backtracking with Used Set pattern from the Backtracking topic, and you can replay every step in the interactive Permutations animation.
Given an array of distinct numbers, return all possible orderings. For n numbers there are n factorial permutations.
For 1, 2, 3, there are 6 permutations, from 1, 2, 3 to 3, 2, 1.
Writing nested loops only works for a fixed n. Backtracking builds one position at a time for any n.
At each level, try every number that is not used yet. Mark it as used, recurse to fill the next position, then unmark it. When the path has n numbers, record it.
Pick 1, then 2, then 3, and record 1, 2, 3. Undo 3 and 2, pick 3 then 2, and record 1, 3, 2. Undo back to the root and pick 2, giving 2, 1, 3 and 2, 3, 1. Then pick 3, giving 3, 1, 2 and 3, 2, 1. All 6 permutations are found.
In code, if the path size equals n, add a copy. Otherwise loop over all numbers, skip used ones, then choose, recurse and un-choose. There are n factorial leaves, so it's O of n times n factorial.
Remember: permutations use a used array instead of a start index. Every unused number can go in the next position.