Backtracking: all permutations

Given a list of distinct numbers, produce every possible ordering — every permutation. For [1, 2, 3] there are 3! = 6 of them.

This is the textbook case for backtracking: build a partial arrangement one choice at a time, recurse deeper, and when you hit a dead end (or a complete arrangement) undo your last choice and try the next option. Think of it as a decision tree — at each level you pick one of the still-unused numbers.

Picture the choices as a tree. You start with nothing placed; at each level you pick one unused number and recurse on the rest:

[]
├─ 1 ─┬─ 2 ─ 3   → [1, 2, 3]
│     └─ 3 ─ 2   → [1, 3, 2]
├─ 2 ─┬─ 1 ─ 3   → [2, 1, 3]
│     └─ 3 ─ 1   → [2, 3, 1]
└─ 3 ─┬─ 1 ─ 2   → [3, 1, 2]
      └─ 2 ─ 1   → [3, 2, 1]

Each leaf (every number used) is one complete permutation. The "undo" is just returning from the recursion and trying the next branch.

Determinism note: the order permutations come out depends on how you recurse, so to keep the grader happy this lesson returns the sorted list of permutations. Wrap your final result in sorted(...) — Python sorts lists lexicographically, so [1, 2, 3] comes before [1, 3, 2], and so on.

Your task

Write permute(nums) that returns all permutations of nums as a list of lists, sorted for deterministic order. The empty list has exactly one permutation: the empty arrangement [[]].

permute([1, 2, 3])  # [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
permute([1])        # [[1]]
permute([])         # [[]]
permute([1, 2])     # [[1,2],[2,1]]

Hint: backtrack to collect every ordering, then return sorted(results) so the output order is always the same.