LeetCode 46: given an array of distinct integers nums, return every possible permutation. The example input is 123; the expected output contains 6 arrays — 123, 132, 213, 231, 312, 321. Your job: generate all 6 without hardcoding them.
Why the constraint distinct integers? Because duplicates would change the shape of the tree — an extension we will touch in B4.
Here is a lie I believed for an embarrassingly long time: backtracking is one trick. You learn it once — choose, recurse, unchoose — and then you apply the same trick to every problem that needs a tree. Subsets, permutations, combinations, palindromes. One tool. One template. Done.
The template IS the same. But the TREE is not. And if you try to build permutations with a subset-shaped tree — which is what your instinct will do the first time — the tree will quietly fail to produce 5 of the 6 answers, and you will stare at your output wondering why 213 and 321 are simply nowhere to be found while the sorted 123 shows up just fine.
You know how to list every subset of 123. That was the warmup. Now list every ORDERING of 123. Go ahead — use the same tree you used for subsets. I'll wait.
Decide: include or exclude element 1. Each tap descends one level.