The tell: Every ordering, so position matters and each element is used exactly once.
How you get there
1Track which indices are already used at this depth.
2A complete path of length n is one permutation.
3Un-marking on the way out is what lets sibling branches reuse the element.
Solution
Python
def permute(nums: list[int]) -> list[list[int]]:
out: list[list[int]] = []
path: list[int] = []
used = [False] * len(nums)
def backtrack() -> None:
if len(path) == len(nums):
out.append(path[:])
return
for i, x in enumerate(nums):
if used[i]:
continue
used[i] = True
path.append(x)
backtrack()
path.pop()
used[i] = False # un-choose, or siblings see it as consumed
backtrack()
return out
Time
O(n · n!)
Space
O(n)
What goes wrong
Forgetting to reset used[i] means the first branch consumes everything and later branches find nothing.