• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All integers in nums are distinct
• Every permutation must use every element exactly once
• Output size is n!, which is 720 at the maximum input length

Set this beside Combinations before writing anything, because the two problems look similar and the difference between them determines the entire solution.

Combinations asks which elements to select, and rearranging a selection produces nothing new. Permutations asks how to arrange elements, and rearranging is the only thing that produces anything new. Every element is used in every answer; only position varies.

That single difference removes one mechanism and requires another.

Combinations avoided duplicates by only ever choosing numbers larger than the last one taken, forcing every path into increasing order so each set had exactly one representation.

Apply that here and it destroys the problem. Forcing increasing order means [1,2,3] is buildable but [2,1,3] is not — yet [2,1,3] is a required answer. The very orderings the start index suppresses are the ones we now need.

So the constraint has to be dropped. At every position, any element is a legal choice.

Any element, that is, except the ones already placed. A permutation uses each element exactly once, so the restriction is no longer "later than the last choice" but "not already used". Different question, different bookkeeping.

Maintain a parallel array of booleans, one per element, recording whether it currently sits in the path. Before choosing an element, check it; after backtracking, release it.

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

    def build():
        if len(path) == len(nums):
            result.append(list(path))     # all slots filled: snapshot a copy
            return

        for i in range(len(nums)):
            if used[i]:
                continue                  # already placed on this path
            used[i] = True                # CHOOSE
            path.append(nums[i])
            build()                       # EXPLORE
            path.pop()                    # UN-CHOOSE
            used[i] = False               # release for other branches

    build()
    return result

Count the branching rather than asserting the formula. At the first slot every element is available, giving n choices. Whichever is taken, the second slot has n-1 remaining, then n-2, and so on down to 1.

Multiplying: n × (n-1) × (n-2) × … × 1 = n!

Note the branching factor shrinks by one at each level, which is what distinguishes this tree from the subsets tree, where every level branched exactly twice. Producing each permutation also costs O(n) to copy, so the total is O(N × N!).

The n = 6 constraint is a deliberate signal. At 6 the answer has 720 entries; at 13 it would exceed a billion. When you see a tiny bound like this, the problem is telling you that exhaustive enumeration is the intended solution.

Following the first complete branch and the first backtrack in full:

Six permutations. Watch the moment marked above: releasing index 1 after the [1,2,…] subtree is what allows 2 to be reused in [1,3,2]. Skip that release and the search would produce [1,2,3] and then quietly stop finding anything else.

There is a second formulation that needs no auxiliary array. Rather than building a separate path, treat the input itself as the permutation under construction. At position i, swap each candidate from the remaining suffix into place, recurse on position i+1, then swap back.

def permute(nums):
    result = []

    def build(i):
        if i == len(nums):
            result.append(list(nums))     # nums IS the current permutation
            return
        for j in range(i, len(nums)):
            nums[i], nums[j] = nums[j], nums[i]     # CHOOSE
            build(i + 1)                            # EXPLORE
            nums[i], nums[j] = nums[j], nums[i]     # UN-CHOOSE
    build(0)
    return result

The elements before position i are fixed; those from i onward are the unused pool. Swapping is both the choice and the bookkeeping, so no used array is needed — the array's own layout encodes what remains.

It is more elegant and slightly faster. It is also harder to reason about and does not extend cleanly to inputs with duplicates, where the skip-condition is easier to express with an explicit used array. Knowing both, and being able to say why you picked one, is the useful position.

The section's core lesson is now visible. One skeleton, three problems, differing only in the choice space:

Deciding which you are facing reduces to one question: does rearranging an answer produce a different answer? If no, impose an ordering with a start index. If yes, track usage instead.

Train the reflex: order matters means no start index and a used array. Order does not matter means a start index and no used array. Getting that backwards produces either duplicates or missing answers, and it is the first thing to settle.