Medium
Backtracking
Permutations
Fix each position by choosing an unused element, then recurse.
Approach
Backtrack building the permutation position by position, marking elements used as you place them and unmarking on the way back. When the current arrangement uses all elements, record it. A used[] array (or swapping in place) prevents reusing an element.
Time complexity
O(n · n!)
Space complexity
O(n)
Common mistake
Forgetting to unmark an element after recursing, which corrupts sibling branches.
See it run, step by step
Generate an interactive lesson for Permutations — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Permutations