Algorithm

Permutations

Backtracking Pattern

Permutations

Given an array of distinct integers, return every possible ordering of those integers.

Every permutation uses all of the elements exactly once — none omitted, none repeated. Two permutations differ if the elements appear in a different sequence, so [1,2,3] and [2,1,3] are both valid and distinct answers.

The output contains n! permutations and may be returned in any order.

CONSTRAINTS
  • 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
EXAMPLE 1
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Six orderings, matching 3! = 6. Unlike combinations, [1,2,3] and [2,1,3] are both present — here rearranging genuinely produces a different answer.
EXAMPLE 2
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Two elements give two orderings. Every element appears in every permutation; the only thing that varies is where.
EXAMPLE 3
Input: nums = [1]
Output: [[1]]
A single element has exactly one ordering. Worth checking that the base case returns a list containing one list, rather than an empty result or a bare value.
EXAMPLE 4
Input: nums = [-1,2,-3]
Output: All 6 orderings of -1, 2 and -3
The values themselves never affect the structure. Permutation count depends only on how many elements there are, so negatives and ordering of the input change nothing about the answer's size or shape.
Are the input integers guaranteed distinct?
Yes here, which keeps the problem clean. With duplicates, [1,1,2] would generate identical permutations by different routes and you would need to sort the input and skip a value when it equals its predecessor and that predecessor is unused — that variant is Permutations II.
Must every permutation use all the elements?
Yes. Permutations of a chosen subset — arrangements of k out of n — is a different problem that combines this technique with a length cutoff.
Does the order of the permutations in the output matter?
No, any order is accepted, so no sorting step is needed. The natural recursion order happens to be lexicographic when the input is sorted, which is convenient but not required.
How large can the output get?
n! grows viciously — 6! is 720, but 10! is over 3.6 million and 13! exceeds a billion. The tight constraint of 6 is a signal that exponential enumeration is expected and acceptable.

An arrangement uses every element, and order is the answer — [1,2,3] and [2,1,3] are both wanted. So there's no "increasing only" trick here (that would throw away answers we need). Instead, at each slot pick any element not already used.

The backtracking template

Every problem in this section is the same loop — three beats: choose, explore, un-choose.

python
def backtrack(state):
    if done(state):
        save(state)              # record the finished answer
        return
    for choice in choices(state):    # what can I pick right now?
        if not ok(choice):
            continue                 # prune: skip bad picks early
        apply(choice)                # CHOOSE
        backtrack(next_state)        # EXPLORE
        undo(choice)                 # UN-CHOOSE: put it back

Only four slots change between problems: done, choices, ok (pruning), and how you finish (save every answer, or return True at the first one). Fill those and the problem is solved.

What changes here
- A choice = place an element that isn't in the path yet.
- Choices = every index i with used[i] == False.
- Done = path length == n → save it.
- Prune = skip elements already used.
python
def permute(nums):
    res, path = [], []
    used = [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):
            res.append(list(path))
            return
        for i in range(len(nums)):
            if used[i]:
                continue              # already placed
            used[i] = True            # CHOOSE
            path.append(nums[i])
            backtrack()               # EXPLORE
            path.pop()                # UN-CHOOSE
            used[i] = False           # release it

    backtrack()
    return res

Undo both things: pop the path and set used[i] = False. Forgetting the release is the classic bug — elements get eaten and you end up with almost no permutations. Note there's no start index here; looping from 0 every time is exactly what produces the reorderings.

Trace [1,2,3]: fix 1 → [1,2,3],[1,3,2]; fix 2 → [2,1,3],[2,3,1]; fix 3 → [3,1,2],[3,2,1]. n! = 6.

Interactive Strategy Visualization

The Arrangement Tree

Visualizing how the seating chart evolves with each pick.

START[]PICK 1PICK 2PICK 2PICK 1
Current Seat
Full Line-up
Start with all people standing. Every person is a candidate for the first chair.
THE USED POOL

Once a number is in a chair, it's Busy. We can't pick it again until it "stands up" (backtracks) and becomes Available once more.

ORDER MATTERS

Unlike subsets, picking [1, 2] and [2, 1] are two completely different realities. Every branch of the tree must lead to a full line-up.

O(Nⁿ) Generate All Sequences Then Filter
→
O(N × N!) Used-Array Backtracking
→
O(N × N!) In-place Swapping