46. Permutations — DSA Atlas

MediumBacktrackingBacktracking with a used[] markerPermutation generation

Permutations

Given an array nums of distinct integers, return all possible permutations. You can return the answer in any order.

In plain English

List every distinct ordering of the input elements, using each element exactly once per ordering.

Picture it like this

Seating 3 guests in 3 chairs: for the first chair you have 3 choices, then 2, then 1, tracing out all 6 seating arrangements.

Example

Input: nums = [1, 2, 3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Why: There are 3! = 6 orderings of three distinct elements, and each appears exactly once.

Constraints

1 <= nums.length <= 6-10 <= nums[i] <= 10All the integers of nums are unique

Pattern lesson

See the pattern, then code

Permutation generation

↗

Backtracking

Generate every valid combination, permutation, partition, or configuration.. A permutation uses every element exactly once, so unlike subsets we scan all indices each level and only skip those already placed. A used[] boolean array marks which elements are currently in the path.

New words, made simpleKnow these before the algorithm

Permutation: An ordered arrangement using every element once; order distinguishes permutations from combinations.
used[] array: Booleans tracking which elements are already placed in the current path so none is reused.
Depth = n: The base case: a complete permutation has been built once the path length matches the input length.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Insert-into-every-gap recursion

Correct but copies many intermediate lists, using more memory than needed.

Build permutations of the first k elements, then insert the next element into each possible gap.

Time O(n * n!)Space O(n * n!)

Best choiceBacktracking with used[]

In-place path with only a boolean array of overhead; the clean, standard template.

At each depth pick any unused element, mark it used, recurse, then release it.

Time O(n * n!)Space O(n)

The rule we keep true

Invariant

At every call, path is a duplicate-free sequence of placed elements and used[i] is True exactly for the elements currently in path.

Why this is correct

Reasoning

Each level chooses one not-yet-used element, so after n levels every element appears exactly once, giving a valid permutation. Because every unused index is tried at every level, all n! orderings are reached; the paired mark/unmark keeps used[] consistent so no branch leaks state into another.

The algorithm in three movesSay these aloud before coding

1When the path length equals n, record a copy as a finished permutation

path=[1] used={0}

2Loop over every index; skip indices whose used flag is set

path=[1,2] used={0,1}

3Mark used, append, recurse, then unmark and pop to restore state

path=[1,2,3] -> record

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readpath=[]

2 · AskWhich first element?

3 · Update stateused=[F,F,F]

4 · ResultPick 1, used[0]=T

Key takeaway

Fixing 1 first, the subtree yields [1,2,3] and [1,3,2] before backtracking to fix 2.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 7-10Completion check
When path has n elements the permutation is complete; store a copy and return.
2
Lines 11-13Skip placed elements
Iterate every index and skip any already in the path via the used flag.
3
Lines 14-18Mark, recurse, restore
Set used[i], push nums[i], recurse to the next depth, then pop and clear used[i] to try the next choice.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single element -> [[x]]
Two elements -> two permutations
Negative numbers are handled identically since values are only placed, never compared

Common beginner mistakes

Forgetting to reset used[i] = False after recursion, which blocks later branches
Appending path without copying so all results alias one list
Using a start index (that would generate combinations, not permutations)

Check your understanding

Why is there no start index here, unlike in the subsets and combination-sum solutions?

PyPython 3 · solution.py

Optimal

1class Solution:2    def permute(self, nums: list[int]) -> list[list[int]]:3        res: list[list[int]] = []4        path: list[int] = []5        used = [False] * len(nums)67        def backtrack() -> None:8            if len(path) == len(nums):9                res.append(path[:])10                return11            for i in range(len(nums)):12                if used[i]:13                    continue14                used[i] = True15                path.append(nums[i])16                backtrack()17                path.pop()18                used[i] = False1920        backtrack()21        return res

Time complexityO(n * n!)Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

MetaAmazonMicrosoftLinkedIn

Permutations

Permutations

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Backtracking