List every ordering by filling positions one at a time: pick an item that is not used yet, recurse to fill the rest, then un-choose it (pop it and mark it free) and try the next unused item. Position 1 has n choices, position 2 has n − 1, and so on, so the tree has n × (n − 1) × … × 1 = n! leaves, one per order.
- Average time
- O(n·n!)
- Space
- O(n)