0
Challenge · 48Recursion & Backtracking
Permutations
Recursionused in ~85% of apps
Same skeleton, one change: order now matters, so you may look backwards as well as forwards. That single change turns a comfortable 2 to the n into a factorial, and it is why permutation questions always come with a tiny input.
Core idea. A permutation uses every item exactly once in some order. Because order matters, the loop starts from 0 rather than from a start position, and something has to remember which items are already in the path. The cost is n factorial, which grows far faster than doubling.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
Playground, this isn't a screenshot
every ordering of [1, 2, 3], one move at a time
the path you are holding
1
addadd 1, mark it used
move 0 of 36adds 0 · undos 0
answers recorded so far
nothing yet
Count the adds and the undos as you go. They always end up equal, and that is what backtracking means.
↑ play a little first, then dig in