LeetCode #46 Medium

Permutations

Given an array nums of distinct integers, return all possible permutations (orderings). For [1,2,3] there are 3! = 6.

backtrackingrecursionarray

Open on LeetCode ↗

02

Intuition

💡

Build each ordering slot by slot. For every position, try each number that hasn't been used yet, recurse to fill the next slot, then undo the choice and try the next number.

03

Approach

1

Each permutation fixes a number per slot

A permutation is an arrangement that uses every element exactly once. So think of it as filling slots left to right: for slot 0 choose any number, for slot 1 any of the remaining, and so on. The branching factor shrinks by one each level until a full ordering is complete.

2

Track which numbers are used

Carry a used flag set (or boolean list). At each level, loop over all numbers and skip the ones already on the path. Pick an unused number, mark it used, append it, and recurse. This guarantees no value repeats within a single permutation.

3

Record at the leaf, then backtrack

When the path length equals the input length, every slot is filled — record a copy of the path. After each recursive call, pop the number and clear its used flag so the next iteration can try it elsewhere. That choose → explore → un-choose loop is the heart of backtracking. There are n! leaves.

04

Solution & live demo

python

▶1class Solution:
▶2    def permute(self, nums):
▶3        res = []
▶4        used = [False] * len(nums)
▶5        def backtrack(path):
▶6            if len(path) == len(nums):
▶7                res.append(path[:])
▶8                return
▶9            for i in range(len(nums)):
▶10                if used[i]:
▶11                    continue
▶12                used[i] = True
▶13                path.append(nums[i])
▶14                backtrack(path)
▶15                path.pop()
▶16                used[i] = False
▶17        backtrack([])
▶18        return res

05

Edge cases

Single element

One permutation, the list itself.

Empty input

Returns [[]] — one permutation, the empty ordering.

Distinct values assumed

With duplicates you'd get repeated permutations; Permutations II adds a sort-and-skip to dedupe.

06

Complexity

Time

O(n·n!)

Space

O(n)

n! permutations, each O(n) to build and copy; recursion depth is n.