Generate all permutations of a list of distinct integers using backtracking.

How to think about it

The interviewer almost certainly knows itertools.permutations exists — handing them that is not the answer they’re after. What they’re probing is whether you can construct the search yourself: choose, recurse, undo. That choose-explore-unchoose rhythm is the backbone of every backtracking problem, and permutations are the cleanest place to show you own it rather than borrow it from a library.

The mechanism is a recursion that grows one ordering at a time. At each level you hold a partial path and ask “which element goes next?” The twist that makes this permutations and not subsets is the candidate set: order matters, so any element you haven’t placed yet is fair game, not just the ones to the right. You track that with a used flag per index. You pick an unused element, append it, mark it used, and recurse to fill the remaining slots. When the path reaches full length you’ve built one complete permutation, so you snapshot it. Then — and this is the move people drop — you undo both actions: pop the element and clear its used flag, so the slot is clean for the next candidate. That restore is what lets the same path and used arrays serve every branch of the tree instead of allocating fresh state each time.

A worked example

def permute(nums):
    result = []
    used = [False] * len(nums)

    def backtrack(path):
        if len(path) == len(nums):
            result.append(list(path))   # snapshot — copy, don't store the live path
            return
        for i in range(len(nums)):
            if used[i]:
                continue                # skip elements already placed
            path.append(nums[i])        # choose
            used[i] = True
            backtrack(path)             # explore
            path.pop()                  # un-choose
            used[i] = False             # restore for the next candidate

    backtrack([])
    return result

print(permute([1, 2, 3]))         # all 3! = 6 orderings
print(len(permute([1, 2, 3, 4]))) # 4! = 24
print(permute([7]))               # single element, one ordering

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
24
[[7]]

Read the six orderings: they come out in a tidy lexicographic-looking order because the loop always tries the lowest unused index first, descends fully, then backtracks to try the next. The count line confirms the shape — four elements yield exactly 24 permutations, the n! you’d expect — and the single-element case shows the base case firing immediately with one ordering. Note the list(path) snapshot: path is mutated in place across the whole traversal, so storing it directly would leave every entry in result pointing at the same list, which ends up empty.