Permutations

Return every ordering of a list of distinct numbers. Each ordering uses every number exactly once.

For [1, 2, 3] there are 3 choices for the first place, 2 for the second and 1 for the last: 3! = 6 orderings.

Build the permutation one place at a time, with used[i] true for each number already in the path.

At each call, try every unused number: mark it used, append it, recurse, then pop it and mark it free again. Undoing the choice puts everything back as it was, so the next number starts clean.

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

    def backtrack():
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return result

used makes the check constant time. Testing nums[i] in path works too, but scans the path every time.

Run it on [1, 2, 3].

The first call tries 1. Below it, 1 is used, so 2 and then 3 take the second place, and each branch ends on the one number left: [1, 2, 3], then [1, 3, 2].

Undoing 1 frees it, and the first call tries 2, then 3, the same way. The tree has 16 calls, and its 6 leaves are the answers.

• Undo both changes: pop the path and set used[i] back to False. Forget one and later branches go missing.
• Record a copy, path[:], not path, and only when the path is full.
• With a repeated number, [1, 1, 2] gives each ordering twice. Permutations II skips a repeat at the same depth.
• The output grows as n!: four numbers already make 24.

There are n! permutations, and copying each into the result takes O(n), so time is O(n · n!). The tree's inner calls add less than that.

Apart from the output, space is the path, used and the call stack, all O(n).