Permutations
Enumerate every ordering by choosing an unused element, recursing, then un-choosing. The choose/explore/un-choose pattern is the backtracking template itself.
- Category
- Backtracking
- Time complexity
- O(n!)
- Space complexity
- O(n)
Pseudocode
choose an unused letter recurse with it fixed un-choose (backtrack) n! leaves = n! permutations
Reference implementation
def perm(path):
if len(path) == n:
out.append(path); return
for ch in unused:
perm(path + ch)